动态规划入门与状态转移

一、动态规划概述

1.1 核心思想

分解子问题 + 记忆化 + 递推求解

将大问题分解为重叠子问题，存储子问题的解避免重复计算。

1.2 DP三要素

1. 状态定义：dp[i] 表示什么含义
2. 状态转移方程：dp[i] 与 dp[i-1], dp[i-2] … 的关系
3. 初始状态：边界条件的值

1.3 DP vs 递归 vs 贪心

特性	递归	贪心	动态规划
子问题重叠	重复计算	不涉及	记忆化避免重复
选择	遍历所有	局部最优	保存所有子问题最优
最优性	可能最优	不一定	保证最优

二、解题步骤

2.1 四步法

1. 定义状态：明确dp数组的含义
2. 找转移方程：分析状态如何转移
3. 初始化：确定边界条件
4. 确定遍历顺序：确保所需状态已计算

三、经典入门问题

3.1 斐波那契数列

// 递归 - O(2ⁿ)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// 记忆化 - O(n)
int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// 动态规划 - O(n), O(1)空间
int fibDP(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

3.2 爬楼梯

问题：n阶楼梯，每次爬1或2步，有多少种方法。

状态：dp[i] = 爬到第i阶的方法数

转移：dp[i] = dp[i-1] + dp[i-2]

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

3.3 不同路径

问题：m×n网格，从左上到右下，只能右或下，路径数。

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

3.4 最长递增子序列(LIS)

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

转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; 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;
}

( O(n^2) )，可优化到 ( O(n \log n) ) 用二分查找。

3.5 最大子数组和

状态：dp[i] = 以nums[i]结尾的最大子数组和

转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

public int maxSubArray(int[] nums) {
    int maxSum = nums[0], currSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
}

四、空间优化

4.1 滚动数组

当状态只依赖于前几个状态时，可用变量替代数组。

// 斐波那契
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
}

五、总结

动态规划的关键是找到正确的状态定义。一旦状态定义清晰，转移方程往往自然浮现。记住DP的核心：大事化小，小事化了，记忆结果，避免重复。