📚 动态规划经典问题课堂笔记

🎒 01背包问题（基础版）

问题描述

有n个物品和一个容量为m的背包，每个物品有重量w[i]和价值v[i]，每个物品只能选一次，求背包能装下的最大价值。

核心定义

• 状态定义：dp[i][j] 表示只考虑前i个物品，背包承重上限为j时的最大价值
• 状态转移：
  • 当j < w[i]（装不下第i个物品）：只能不选，dp[i][j] = dp[i-1][j]
  • 当j >= w[i]（能装下第i个物品）：选或不选取最大值，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

带关键注释代码

#include<bits/stdc++.h>
const int N = 2e5+10;
using namespace std;

// dp[i][j]: 前i个物品，背包容量j时的最大价值
int n, m, dp[40][210], w[N], v[N];

int main() {
    // 输入：背包容量m，物品数量n
    cin >> m >> n;
    // 输入每个物品的重量和价值
    for(int i=1; i<=n; i++) {
        cin >> w[i] >> v[i];
    }
    
    // 动态规划核心：逐个物品考虑
    for(int i=1; i<=n; i++) {
        // 逐个容量考虑
        for(int j=1; j<=m; j++) {
            if(j < w[i]) {
                // 装不下第i个物品，只能继承前i-1个物品的结果
                dp[i][j] = dp[i-1][j];
            } else {
                // 能装下，取"不选"和"选"两种情况的最大值
                // 不选：dp[i-1][j]
                // 选：前i-1个物品用j-w[i]容量，加上第i个物品的价值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    
    // 输出最终结果：前n个物品，容量m时的最大价值
    cout << dp[n][m];
    return 0;
}

🎒 01背包问题（方案数统计版）

问题描述

在基础01背包问题上，额外求达到最大价值的方案总数，结果对1e9+7取模。

核心定义

• 新增状态：f[i][j] 表示考虑前i个物品，背包承重上限为j时，达到最大价值的方案总数
• 状态转移：
  • 当j < w[i]：只能不选，方案数继承
  • 当j >= w[i]：比较选与不选的价值，方案数取对应情况
  • 若两者价值相等：方案数相加
• 初始化：f[i][0] = 1（所有物品都不选，只有1种方案）

带关键注释代码

#include<bits/stdc++.h>
const int N = 2e5+10, M = 1e9+7;
using namespace std;

// dp[i][j]: 前i个物品，容量j时的最大价值
// f[i][j]: 达到该最大价值的方案总数
int n, m, w[N], v[N], dp[1010][1010], f[1010][1010];

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> w[i] >> v[i];
    }
    
    // 关键初始化：容量为0时，无论多少物品，都只有1种方案（什么都不选）
    for(int i=0; i<=n; i++) f[i][0] = 1;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(j < w[i]) {
                // 装不下，价值和方案数都继承
                dp[i][j] = dp[i-1][j];
                f[i][j] = f[i-1][j];
            } else {
                // 比较不选和选的价值
                if(dp[i-1][j] > dp[i-1][j-w[i]] + v[i]) {
                    // 不选更好，方案数取不选的情况
                    dp[i][j] = dp[i-1][j];
                    f[i][j] = f[i-1][j];
                } else if(dp[i-1][j] < dp[i-1][j-w[i]] + v[i]) {
                    // 选更好，方案数取选的情况
                    dp[i][j] = dp[i-1][j-w[i]] + v[i];
                    f[i][j] = f[i-1][j-w[i]];
                } else {
                    // 两者价值相等，方案数相加
                    dp[i][j] = dp[i-1][j];
                    f[i][j] = f[i-1][j] + f[i-1][j-w[i]];
                }
            }
            // 每次计算后取模，防止溢出
            f[i][j] %= M;
        }
    }
    
    // 输出：前n个物品，容量m时达到最大价值的方案数
    cout << f[n][m];
    return 0;
}

📊 分割数组的最大值问题

问题描述

将一个长度为n的数组分成K个连续的子数组，使得这些子数组的和的最大值最小。

核心定义

• 前缀和：s[i] = s[i-1] + a[i]，快速计算任意区间和
• 状态定义：dp[i][j] 表示前i个位置分成j个部分时，最大值的最小值
• 状态转移：枚举最后一个部分的起始位置k，取所有划分策略中的最小值
• 初始化：dp[i][1] = s[i]（前i个元素分成1个部分，最大值就是总和）

带关键注释代码

#include<bits/stdc++.h>
const int N = 2e5+10;
using namespace std;

// dp[i][j]: 前i个元素分成j个连续部分，各部分和的最大值的最小值
int K, dp[1010][60], s[N], a[N], n;

int main(){
    cin >> n >> K;
    // 初始化dp数组为无穷大（因为要求最小值）
    memset(dp, 0x3f, sizeof dp);
    
    // 输入数组并计算前缀和
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    
    // 边界条件：分成1个部分时，最大值就是前i个元素的总和
    for(int i=1; i<=n; i++) dp[i][1] = s[i];
    
    // 动态规划核心
    for(int i=1; i<=n; i++){ // 考虑前i个元素
        for(int j=2; j<=min(K, i); j++){ // 分成j个部分（j最多为i，每个部分1个元素）
            // 枚举最后一个部分的起始位置k
            // 前k-1个元素分成j-1个部分，k到i是第j个部分
            for(int k=j; k<=i; k++){
                // 计算最后一个部分的和
                int last_sum = s[i] - s[k-1];
                // 这种划分策略下的最大值 = max(前j-1部分的最大值, 最后一部分的和)
                int current_max = max(dp[k-1][j-1], last_sum);
                // 取所有策略中的最小值
                dp[i][j] = min(dp[i][j], current_max);
            }
        }
    }
    
    // 输出最终结果：前n个元素分成K个部分的最优解
    cout << dp[n][K];
    return 0;
}

💰 最小费用背包问题

问题描述

有n个物品，每个物品有价格w[i]和容量v[i]，每个物品只能买一次。求恰好获得总容量L时的最小花费。如果无法恰好获得L容量，输出"no solution"。

核心定义

• 状态定义：dp[i][j] 表示前i个物品，恰好获得容量j时的最小花费
• 状态转移：
  • 当j < v[i]：只能不买，dp[i][j] = dp[i-1][j]
  • 当j >= v[i]：取"不买"和"买"两种情况的最小值
• 初始化：dp[i][0] = 0（容量为0时花费为0），其余初始化为无穷大

带关键注释代码

#include<bits/stdc++.h>
const int N = 2e5+10;
using namespace std;

// dp[i][j]: 前i个物品，恰好获得容量j时的最小花费
int dp[510][2010], n, L, w[N], v[N];

int main(){
    // 初始化dp数组为无穷大（因为要求最小值）
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> L;
    
    // 关键初始化：容量为0时，无论多少物品，花费都是0
    for(int i=0; i<=n; i++) dp[i][0] = 0;
    
    // 输入每个物品的价格和容量
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }
    
    // 动态规划核心
    for(int i=1; i<=n; i++){
        for(int j=1; j<=L; j++){
            if(j < v[i]) {
                // 容量不够买第i个物品，只能不买
                dp[i][j] = dp[i-1][j];
            } else {
                // 容量足够，取"不买"和"买"两种情况的最小值
                // 不买：dp[i-1][j]
                // 买：前i-1个物品获得j-v[i]容量，加上第i个物品的价格
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }
    
    // 判断是否有解
    if(dp[n][L] == 0x3f3f3f3f) {
        cout << "no solution";
    } else {
        cout << dp[n][L];
    }
    return 0;
}

💡 核心易错点总结

1. 01背包与完全背包的区别：01背包每个物品只能选一次，状态转移用dp[i-1]；完全背包每个物品可以选多次，状态转移用dp[i]
2. 初始化方向：求最大值时初始化为0，求最小值时初始化为无穷大
3. 边界条件：特别注意容量为0或物品数为0的情况
4. 取模时机：方案数统计问题中，每次加法后都要取模，防止整数溢出
5. 连续划分问题：必须保证子数组是连续的，因此用前缀和+枚举划分点的方式