动态规划模板：从状态定义到转移方程的完整套路#

动态规划最难的地方，从来不是写代码，而是想明白“状态”到底是什么。一旦状态定义正确，题目往往就顺下来了。

⚡ 速记版模板#

// 模板用途：将原问题拆成子问题，按状态转移自底向上求解
for (状态1初始化) { // 初始化第一类基础状态（如 dp[0]、第一行、第一列）
}
for (状态2初始化) { // 初始化第二类基础状态（按题意补齐边界）
}
for (状态遍历顺序) { // 按依赖关系遍历，保证转移来源已计算
    dp[i] = 状态转移; // 根据状态定义写转移方程
}
return dp[目标状态]; // 返回题目要求的最终状态值

java

🎯 什么时候想到动态规划？#

当题目有以下特征时，优先考虑动态规划：

求最优解：最大值、最小值、方案数、可行性
问题可以拆成重复子问题
当前答案依赖之前阶段的结果

Hot 100 里的典型题目：

💡 动态规划五步法#

推荐每次都按这个顺序想：

dp[i] 或 dp[i][j] 表示什么
状态转移方程是什么
初始值怎么设
遍历顺序怎么定
是否可以滚动优化

🚀 模板一：一维线性 DP#

适合：

爬楼梯
打家劫舍
完全平方数
零钱兑换

class Solution {
    public int solve(int n) {
        int[] dp = new int[n + 1]; // dp[i]：规模为 i 时的最优解/方案数（具体含义由题目定义）

        dp[0] = 0; // 基础状态：空规模或起点状态

        for (int index = 1; index <= n; index++) { // 从小到大计算，确保依赖项已就绪
            dp[index] = transition(dp, index); // 用已知小规模状态转移得到当前状态
        }

        return dp[n]; // 返回目标状态
    }

    private int transition(int[] dp, int index) {
        return 0; // 模板占位：按题意实现转移逻辑（如 max/min/加和/布尔）
    }
}

java

常见思路#

dp[i] 表示到位置 i 的最优解
当前状态通常由前 1 个、前 2 个或若干更小状态转移而来

🚀 模板二：背包型 DP#

适合：

零钱兑换
分割等和子集
完全平方数

class Solution {
    public boolean canPartition(int[] nums, int capacity) {
        boolean[] dp = new boolean[capacity + 1]; // dp[c]：容量 c 是否可由若干元素恰好凑出
        dp[0] = true; // 容量 0 永远可达（什么都不选）

        for (int num : nums) { // 依次处理每个物品（每个数只能用一次）
            for (int current = capacity; current >= num; current--) { // 倒序遍历容量：防止同一轮重复使用当前 num
                dp[current] = dp[current] || dp[current - num]; // 不选 num 或选 num 两种情况
            }
        }

        return dp[capacity]; // 目标容量是否可达
    }
}

java

关键点：

0/1 背包通常倒序遍历容量
完全背包通常正序遍历容量

🚀 模板三：二维网格 DP#

适合：

不同路径
最小路径和

class Solution {
    public int solve(int[][] grid) {
        int rows = grid.length; // 网格行数
        int cols = grid[0].length; // 网格列数
        int[][] dp = new int[rows][cols]; // dp[row][col]：走到该格子的最小路径和（或题目定义值）

        dp[0][0] = grid[0][0]; // 起点初始化

        for (int row = 0; row < rows; row++) { // 按行遍历
            for (int col = 0; col < cols; col++) { // 按列遍历
                if (row == 0 && col == 0) { // 起点已初始化，无需转移
                    continue;
                }

                int fromUp = row > 0 ? dp[row - 1][col] : Integer.MAX_VALUE / 2; // 上方来源，不存在时给极大值避免被选中
                int fromLeft = col > 0 ? dp[row][col - 1] : Integer.MAX_VALUE / 2; // 左侧来源，不存在时给极大值
                dp[row][col] = Math.min(fromUp, fromLeft) + grid[row][col]; // 当前值 = 最优来源 + 当前格代价
            }
        }

        return dp[rows - 1][cols - 1]; // 终点状态即答案
    }
}

java

🚀 模板四：区间 / 字符串 DP#

适合：

最长回文子串
编辑距离
最长公共子序列
最长有效括号

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int rows = text1.length(); // 字符串1长度
        int cols = text2.length(); // 字符串2长度
        int[][] dp = new int[rows + 1][cols + 1]; // dp[i][j]：text1前 i 个与 text2前 j 个的 LCS 长度

        for (int row = 1; row <= rows; row++) { // i 从 1 开始，方便映射到字符下标 i-1
            for (int col = 1; col <= cols; col++) { // j 同理
                if (text1.charAt(row - 1) == text2.charAt(col - 1)) { // 当前字符相同，可把公共子序列长度 +1
                    dp[row][col] = dp[row - 1][col - 1] + 1; // 来源是左上角状态
                } else { // 当前字符不同，只能舍弃其中一个字符
                    dp[row][col] = Math.max(dp[row - 1][col], dp[row][col - 1]); // 取上或左的较大值
                }
            }
        }

        return dp[rows][cols]; // 全部字符范围内的 LCS 长度
    }
}

java

🧠 常见题型怎么想？#

1. 最值问题#

例如：最大和、最小路径和、最长长度。

通常写法：

dp[i] = Math.max(...) // 最值型 DP：当前状态取多个来源中的最大值

java

或

dp[i] = Math.min(...) // 最值型 DP：当前状态取多个来源中的最小值

java

2. 可行性问题#

例如：能否拆分、能否到达。

通常写法：

dp[i] = dp[j] && condition // 可行性 DP：前置状态可行且当前条件成立，则当前可行

java

3. 计数问题#

例如：共有多少种方案。

通常写法：

dp[i] += dp[j] // 计数型 DP：把所有可转移来源的方案数累加

java

⚠️ 易错点#

状态定义不清
- 写转移前先用一句话定义 dp 的含义
初始化错误
- 很多 DP 错不是错在转移，而是错在第一行、第一列、空串、空数组
遍历顺序错误
- 区间 DP、背包 DP、网格 DP 的顺序都不同
把贪心误写成 DP，或把 DP 误写成贪心
- 如果当前选择会影响未来，通常更偏向 DP

🎨 面试时怎么说#

建议按这个顺序表达：

状态定义
转移来源
初始化
遍历顺序
复杂度

例如：

我定义 dp[i] 表示前 i 个位置时的最优解，那么当前状态可以由前一个或前两个状态转移得到，因此状态方程是……

📌 一句话总结#

动态规划的关键不是背题，而是学会稳定地问自己五个问题：

状态是什么？
怎么转移？
初始值是什么？
顺序怎么遍历？
能不能优化空间？