CONTEST ID : 1473 - C++ 动态规划

一、动态规划核心思想

1. 三大条件

1. 最优子结构：大问题最优解由子问题最优解推出
2. 重叠子问题：重复计算子问题，用数组 / 备忘录缓存避免重复
3. 无后效性：当前状态仅依赖之前状态，未来不影响过去

2. 解题四步

1. 定义状态 dp[i]：子问题含义
2. 推导状态转移方程（核心）
3. 初始化边界条件
4. 循环计算 / 记忆化递归求解

3. 两种实现方式

• 记忆化搜索（递归 + 备忘录）：自上而下，思路直观
• 递推（循环 DP）：自下而上，效率更高，常用

例题 1：斐波那契数列

题意

(f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2))
方法 1：记忆化 DP（递归）

#include <iostream>
#include <vector>
using namespace std;

vector<int> dp;
int fib(int n) {
    if (n <= 2) return 1;
    if (dp[n] != 0) return dp[n]; // 已计算直接返回
    dp[n] = fib(n-1) + fib(n-2);  // 状态转移
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    dp.resize(n+1,  0);
    cout << fib(n);
    return 0;
}

方法 2：递推 DP（最优）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> dp(n+1);
    dp[1] = dp[2] = 1; // 边界初始化
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 转移方程
    }
    cout << dp[n];
    return 0;
}

例题 2：爬楼梯

题意

一次爬 1/2 阶，求 n 阶楼梯多少种走法 
状态：dp[i] = 爬到第 i 阶方案数 
转移：dp[i] = dp[i-1] + dp[i-2] 
边界：dp[1]=1, dp[2]=2

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> dp(n+1);
    dp[1] = 1;
    if(n>=2) dp[2] = 2;
    for(int i=3;i<=n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n];
    return 0;
}

01 背包（最经典 DP 模型）

题意

背包容量 V，n 件物品，每件重量 w [i]、价值 v [i]，每件只能选一次，求最大价值

状态定义

dp[i][j]：前 i 件物品，容量 j 时最大价值

转移方程

1. 不选第 i 件：dp[i][j] = dp[i-1][j]
2. 选第 i 件（j>=w [i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i] 取两者最大值：

(dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]))
基础二维代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;
    vector<int> w(n+1), v(n+1);
    for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
    
    vector<vector<int>> dp(n+1, vector<int>(V+1, 0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=V;j++){
            dp[i][j] = dp[i-1][j]; // 不选
            if(j >= w[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    cout << dp[n][V];
    return 0;
}

空间优化一维滚动数组（标准写法）

逆序遍历防止物品重复选取

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;
    vector<int> w(n+1), v(n+1);
    for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
    
    vector<int> dp(V+1, 0);
    for(int i=1;i<=n;i++){
        // 逆序
        for(int j=V;j>=w[i];j--){
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[V];
    return 0;
}

完全背包（物品无限选）

内层循环正序：

for(int i=1;i<=n;i++){
    for(int j=w[i];j<=V;j++){
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

SERVER TIME : 2026-09-10 10:30:50
Running Left 703days 01 hours 29 minutes 10 seconds

STATUS : Running    OPEN : Public
Start Time : 2026-08-13 08:00:00
End Time : 2028-08-13 12:00:00