动态规划入门：从斐波那契到背包问题

什么是动态规划？

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题来求解复杂问题的方法。

核心思想

1. 重叠子问题：子问题会被重复计算多次
2. 最优子结构：问题的最优解包含子问题的最优解
3. 无后效性：当前状态一旦确定，之后的演变就不再受之前状态的影响

从斐波那契开始

递归解法（低效）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

问题：时间复杂度 O(2^n)，大量重复计算。

记忆化搜索

int memo[10005];

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 已计算过
    return memo[n] = fib(n - 1) + fib(n - 2);
}

改进：时间复杂度 O(n)，每个子问题只计算一次。

递推解法

int fib(int n) {
    if (n <= 1) return n;
    
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

优化空间：

int fib(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return curr;
}

DP 解题步骤

1. 定义状态

用 dp[i] 表示什么？通常是问题的子问题的答案。

2. 确定转移方程

找出 dp[i] 与 dp[j]（j < i）之间的关系。

3. 确定初始条件和边界

最小的子问题如何解决？

4. 确定计算顺序

从小到大还是从大到小？

经典问题：爬楼梯

问题：有 n 级台阶，每次可以爬 1 级或 2 级，有多少种方法爬到顶部？

分析

• 到达第 n 级，可以从第 n-1 级爬 1 级，或从第 n-2 级爬 2 级
• 所以 dp[n] = dp[n-1] + dp[n-2]

代码

int climbStairs(int n) {
    if (n <= 2) return n;
    
    int dp[n + 1];
    dp[1] = 1;  // 1 种方法：爬 1 级
    dp[2] = 2;  // 2 种方法：1+1 或 2
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

经典问题：最长递增子序列（LIS）

问题：给定数组，求最长严格递增子序列的长度。

分析

• dp[i] = 以第 i 个元素结尾的最长递增子序列长度
• 对于每个 i，检查所有 j < i，如果 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)

代码 O(n²)

int lengthOfLIS(vector<int>& a) {
    int n = a.size();
    vector<int> dp(n, 1);  // 每个元素本身就是长度为 1 的子序列
    
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    
    return ans;
}

优化 O(n log n)

使用二分查找优化：

int lengthOfLIS(vector<int>& a) {
    vector<int> tails;  // tails[i] = 长度为 i+1 的最小末尾元素
    
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    
    return tails.size();
}

经典问题：背包问题

01 背包

问题：有 n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 W。每个物品只能选一次，求最大价值。

分析

• dp[i][j] = 考虑前 i 个物品，背包容量为 j 时的最大价值
• 对于第 i 个物品，选或不选：
  • 不选：dp[i][j] = dp[i-1][j]
  • 选：dp[i][j] = dp[i-1][j-w[i]] + v[i]（前提：j >= w[i]）

代码

int knapsack01(int n, int W, int w[], int v[]) {
    int dp[n + 1][W + 1] = {0};
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];  // 不选第 i 个物品
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    
    return dp[n][W];
}

空间优化

int knapsack01(int n, int W, int w[], int v[]) {
    int dp[W + 1] = {0};
    
    for (int i = 1; i <= n; i++) {
        // 注意：必须倒序遍历，避免重复选择
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

完全背包

问题：每个物品可以选择无限次。

int knapsackComplete(int n, int W, int w[], int v[]) {
    int dp[W + 1] = {0};
    
    for (int i = 1; i <= n; i++) {
        // 注意：正序遍历，允许重复选择
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[W];
}

多重背包

问题：第 i 个物品最多选 c[i] 次。

二进制优化

将每个物品拆分成若干个"打包物品"：

// 将 c[i] 拆分成 1, 2, 4, 8, ... 个物品
vector<int> newW, newV;
for (int i = 1; i <= n; i++) {
    int k = 1;
    while (c[i] >= k) {
        newW.push_back(k * w[i]);
        newV.push_back(k * v[i]);
        c[i] -= k;
        k *= 2;
    }
    if (c[i] > 0) {
        newW.push_back(c[i] * w[i]);
        newV.push_back(c[i] * v[i]);
    }
}
// 然后用 01 背包求解

经典问题：最长公共子序列（LCS）

问题：求两个字符串的最长公共子序列长度。

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

DP 的常见类型

解题技巧

1. 套路模板

// 1. 定义状态
int dp[状态范围];

// 2. 初始化
memset(dp, 0, sizeof(dp));  // 或其他初始值

// 3. 状态转移
for (/* 遍历所有状态 */) {
    for (/* 遍历所有决策 */) {
        dp[新状态] = max/min(dp[新状态], dp[旧状态] + 代价);
    }
}

// 4. 得到答案
return dp[目标状态];

2. 调试技巧

// 打印 DP 表
for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        cout << dp[i][j] << " ";
    }
    cout << endl;
}

3. 边界检查

• 数组越界？
• 负数下标？
• 初始值正确？

练习建议

---

核心要点：DP 的关键是定义状态和推导转移方程。多练习经典题目，培养"DP 感"！