1. 不相交の線 (LeetCode 1035)

この問題は、一見すると幾何学的な制約があるように見えますが、本質的には「最長共通部分列 (LCS)」を求める問題と同じです。2つの配列間で線を引く際に交差させないという条件は、選ぶ要素の相対的な順序を維持することを意味します。

アルゴリズムの定義

dp[i][j] を、配列 data1 の最初の i 個の要素と、配列 data2 の最初の j 個の要素における最大不相交線数と定義します。

• data1[i-1] == data2[j-1] の場合：dp[i][j] = dp[i-1][j-1] + 1
• 一致しない場合：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

public int maxUncrossedLines(int[] data1, int[] data2) {
    int size1 = data1.length;
    int size2 = data2.length;
    int[][] table = new int[size1 + 1][size2 + 1];

    for (int r = 1; r <= size1; r++) {
        for (int c = 1; c <= size2; c++) {
            if (data1[r - 1] == data2[c - 1]) {
                table[r][c] = table[r - 1][c - 1] + 1;
            } else {
                table[r][c] = Math.max(table[r - 1][c], table[r][c - 1]);
            }
        }
    }
    return table[size1][size2];
}

2. 最大子配列和 (LeetCode 53)

連続する要素からなる部分配列の最大和を求めます。これは1次元の動的計画法で解決可能です。

動的計画法によるアプローチ

dp[i] を、インデックス i で終わる連続部分配列の最大和とします。各要素において、「前の連続和を引き継ぐか」それとも「その要素から新しく開始するか」を選択します。

public int maxSubArray(int[] sequence) {
    if (sequence.length == 0) return 0;
    int n = sequence.length;
    int[] memo = new int[n];
    memo[0] = sequence[0];
    int resultMax = sequence[0];

    for (int i = 1; i < n; i++) {
        memo[i] = Math.max(sequence[i], memo[i - 1] + sequence[i]);
        if (memo[i] > resultMax) resultMax = memo[i];
    }
    return resultMax;
}

貪欲法による最適化

現在の合計が負になった場合、それを捨てて次の要素からカウントをリセットすることで、空間計算量を節約できます。

public int maxSubArrayGreedy(int[] nums) {
    int currentSum = 0;
    int globalMax = Integer.MIN_VALUE;
    for (int val : nums) {
        currentSum += val;
        globalMax = Math.max(globalMax, currentSum);
        if (currentSum < 0) currentSum = 0;
    }
    return globalMax;
}

3. 子配列の判定 (LeetCode 392)

文字列 s が t の部分列であるかを判定します。s の文字順序を保ったまま t から抽出できるかを確認します。

DPによる実装

dp[i][j] を、s の i 文字目までが t の j 文字目までに含まれているかどうかの状態として管理します。

public boolean isSubsequence(String sub, String full) {
    int n = sub.length();
    int m = full.length();
    if (n == 0) return true;
    
    boolean[][] matchTable = new boolean[n + 1][m + 1];
    for (int j = 0; j <= m; j++) matchTable[0][j] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (sub.charAt(i - 1) == full.charAt(j - 1)) {
                matchTable[i][j] = matchTable[i - 1][j - 1];
            } else {
                matchTable[i][j] = matchTable[i][j - 1];
            }
        }
    }
    return matchTable[n][m];
}

4. 異なる部分列 (LeetCode 115)

文字列 s の部分列の中に、文字列 t がいくつ存在するかを数え上げます。一致した場合の遷移が特徴的です。

解法のロジック

dp[i][j] を、s[0...i-1] の中にある t[0...j-1] の出現回数とします。

• s[i-1] == t[j-1] のとき： dp[i][j] = dp[i-1][j-1] (現在の文字をマッチングに使用する) + dp[i-1][j] (現在の文字を使わずに以前の出現回数を引き継ぐ)
• 一致しないとき：dp[i][j] = dp[i-1][j]

public int numDistinct(String source, String target) {
    int sLen = source.length();
    int tLen = target.length();
    int[][] counts = new int[sLen + 1][tLen + 1];

    for (int i = 0; i <= sLen; i++) counts[i][0] = 1;

    for (int i = 1; i <= sLen; i++) {
        for (int j = 1; j <= tLen; j++) {
            if (source.charAt(i - 1) == target.charAt(j - 1)) {
                counts[i][j] = counts[i - 1][j - 1] + counts[i - 1][j];
            } else {
                counts[i][j] = counts[i - 1][j];
            }
        }
    }
    return counts[sLen][tLen];
}