动态规划(DP)算法总结

核心思想

动态规划是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。其核心是：

  • 最优子结构：问题的最优解包含子问题的最优解
  • 重叠子问题：递归过程中会重复计算相同的子问题
  • 状态转移：通过已知状态推导未知状态

DP状态方程设计的五步法

第一步：明确问题类型

  • 最值问题：求最大值、最小值、最长、最短等
  • 计数问题：求方案数、路径数等
  • 存在性问题：判断是否存在某种方案

第二步：定义状态(dp数组含义)

关键原则：状态定义要能够表示子问题的解

常见状态定义模式：

// 1. 以i结尾的最优解
dp[i] = 以nums[i]结尾的最长递增子序列长度

// 2. 前i个元素的最优解  
dp[i] = 前i个数字的最大和

// 3. 从起点到(i,j)的最优解
dp[i][j] = 从(0,0)到(i,j)的最短路径

// 4. 区间[i,j]的最优解
dp[i][j] = 区间[i,j]内的最优解

第三步：找状态转移方程

核心思路：当前状态如何从之前的状态推导而来

通用思考模式：

  1. 枚举选择：当前位置有哪些选择？
  2. 状态依赖：每种选择依赖于哪些之前的状态？
  3. 取最优：在所有选择中取最优值

第四步：确定边界条件

  • 初始状态：最简单子问题的解
  • 边界处理：数组越界、特殊情况等

第五步：确定计算顺序

  • 保证计算当前状态时，依赖的状态已经计算完成
  • 通常是从小到大、从简单到复杂

经典例题：最长递增子序列(LIS)

问题分析

给定数组nums，找到最长严格递增子序列的长度。

状态设计

dp[i] = 以nums[i]结尾的最长递增子序列长度

状态转移推导过程

思考过程：

  1. 当前选择：nums[i]可以接在哪些数字后面？
  2. 条件限制：只能接在比它小的数字后面
  3. 最优策略：在所有可能的接法中选择最长的

转移方程：

dp[i] = max(dp[j] + 1) for all j where j < i and nums[j] < nums[i]

为什么是dp[j] + 1？

  • dp[j]表示以nums[j]结尾的最长序列长度
  • 把nums[i]接在这个序列后面，长度增加1
  • 所以新长度 = dp[j] + 1

完整代码模板

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int maxLen = 1;
    
    // 初始化：每个位置至少长度为1
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        
        // 状态转移：尝试接在前面的数后面
        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;
}

状态转移方程的常见模式

1. 选择型DP

// 每个位置可以选择或不选择
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]); // 打家劫舍

2. 路径型DP

// 从上方或左方转移而来
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; // 最小路径和

3. 匹配型DP

// 字符匹配问题
if (s1[i] == s2[j]) {
    dp[i][j] = dp[i-1][j-1] + 1; // 最长公共子序列
}

4. 区间型DP

// 区间合并问题
for (int len = 2; len <= n; len++) {
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        dp[i][j] = Math.min(dp[i][k] + dp[k+1][j] + cost);
    }
}

调试技巧

1. 手工验证小例子

nums = [1, 3, 2, 4]
dp[0] = 1
dp[1] = 2 (1->3)
dp[2] = 2 (1->2) 
dp[3] = 3 (1->2->4 或 1->3->4)

2. 打印dp数组

System.out.println("dp数组: " + Arrays.toString(dp));

3. 检查边界条件

  • 数组为空
  • 只有一个元素
  • 所有元素相等

时间复杂度优化

LIS的O(nlogn)解法

使用贪心+二分查找：

// tails[i] = 长度为i+1的递增序列的最小尾部元素
int[] tails = new int[nums.length];
int size = 0;

for (int num : nums) {
    int left = 0, right = size;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (tails[mid] < num) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    tails[left] = num;
    if (left == size) size++;
}
return size;

总结要点

  1. 状态定义是关键：要能表示子问题的解
  2. 转移方程要完整：考虑所有可能的转移情况
  3. 边界条件要正确：初始状态和特殊情况
  4. 计算顺序要合理：保证依赖关系
  5. 多练习找规律：不同类型题目的状态设计模式

相关题目

  • 最长递增子序列 (LIS)
  • 最长公共子序列 (LCS)
  • 打家劫舍系列
  • 股票买卖系列
  • 背包问题系列
  • 最小路径和
  • 编辑距离