動的計画法の基本概念

動的計画法（Dynamic Programming、以下DP）は、問題を小さなサブ問題に分解し、その解を記憶して再利用することで効率的に解決するアルゴリズム手法です。この方法は、重複計算を回避し、時間効率を大幅に向上させます。

• dp[k]：サブ問題の解を保持する配列
• 初期条件の設定
• 状態遷移方程式の導出
• メモリ節約のためのローリング変数や配列の活用

代表的な問題

• 階段の登り方
• フィボナッチ数列

DP問題の特徴

• 最適部分構造：元の問題の最適解が、サブ問題の最適解から得られる。
• 無後効性：ある状態が確定すると、その未来の展開は現在の状態のみに依存し、過去の履歴には依存しない。

問題解決手順

1. DP適用の判断
   • バックトラッキング（総当たり）で解決できるか観察。
   • 問題の状態がリスト、行列、または木で表現可能か確認。
   • 最適化問題（最大値、最小値など）を含む場合が多い。
2. 解法ステップ
   • 決定の記述
   • 状態の定義
   • DPテーブルの作成
   • 状態遷移方程式の導出
   • 境界条件の設定

具体的な問題とソリューション

例題1: 階段の登り方

class StairClimb {
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int x = 1, y = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = y;
            y = x + y;
            x = tmp;
        }
        return y;
    }
}

例題2: 動的計画法を使った強盗問題

class HouseRobber {
    public static int rob(int[] houses) {
        if (houses.length == 0) return 0;
        if (houses.length == 1) return houses[0];
        int prevMax = Math.max(houses[0], houses[1]);
        int currentMax = houses[0];
        for (int i = 2; i < houses.length; i++) {
            int temp = prevMax;
            prevMax = Math.max(currentMax + houses[i], prevMax);
            currentMax = temp;
        }
        return Math.max(prevMax, currentMax);
    }
}

例題3: 最長増加部分列

class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

例題4: 最小三角形パス和

class MinTrianglePathSum {
    public static int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] dp = new int[size][size];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < size; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minSum = dp[size - 1][0];
        for (int i = 1; i < size; i++) {
            minSum = Math.min(minSum, dp[size - 1][i]);
        }
        return minSum;
    }
}

例題5: 最大正方形領域

class MaxSquareArea {
    public static int maximalSquare(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (grid[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}