目录

🌟 动态规划核心思想

📌 题目一：P1048 采药（01背包模板）

题目描述

解题思路

代码实现

📌 题目二：P1216 数字三角形（路径最大和）

题目描述

解题思路

代码实现

📌 题目三：P1002 过河卒（棋盘DP）

题目描述

解题思路

代码实现

💡 动态规划四步心法

---

🌟 动态规划核心思想

状态定义 → 转移方程 → 边界处理 → 时空优化
本文精选洛谷动态规划题单中三大经典问题，通过C++与Python双语言对比实现，彻底掌握DP精髓！

---

📌 题目一：P1048 采药（01背包模板）

题目描述

在限定时间T内采集草药，每株草药有采集时间time[i]和价值value[i]，求最大总价值。

解题思路

• 状态定义：dp[j]表示时间j能获得的最大价值

• 转移方程：dp[j] = max(dp[j], dp[j - time[i]] + value[i])

• 遍历顺序：逆序更新（保证每个物品只选一次）

---

代码实现

C++版（滚动数组优化）

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

int main() {
    int T, M;
    cin >> T >> M;
    vector<int> dp(T + 1, 0);
    for (int i = 0; i < M; ++i) {
        int time, value;
        cin >> time >> value;
        for (int j = T; j >= time; --j) {
            dp[j] = max(dp[j], dp[j - time] + value);
        }
    }
    cout << dp[T];
    return 0;
}

Python版（空间压缩）

T, M = map(int, input().split())
dp = [0] * (T + 1)
for _ in range(M):
    time, value = map(int, input().split())
    for j in range(T, time - 1, -1):
        dp[j] = max(dp[j], dp[j - time] + value)
print(dp[T])

---

📌 题目二：P1216 数字三角形（路径最大和）

题目描述

从数字三角形顶层到底层，每次只能向下或右下移动，求最大路径和。

解题思路

• 状态定义：dp[i][j]表示第i行第j列的最大路径和

• 转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]

• 空间优化：使用一维数组从底向上更新

---

代码实现

C++版（二维数组）

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> triangle(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            cin >> triangle[i][j];
    
    for (int i = n-2; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
    
    cout << triangle[0][0];
    return 0;
}

Python版（原地修改）

n = int(input())
triangle = []
for i in range(n):
    triangle.append(list(map(int, input().split())))
for i in range(n-2, -1, -1):
    for j in range(i+1):
        triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
print(triangle[0][0])

---

📌 题目三：P1002 过河卒（棋盘DP）

题目描述

棋盘上卒从(0,0)到(n,m)，马的位置(x,y)及其控制点不可经过，求路径总数。

解题思路

• 状态定义：dp[i][j]表示到达(i,j)的路径数

• 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

• 边界处理：标记马的控制点为障碍

---

代码实现

C++版（动态标记障碍）

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

int dx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));
    dp[0][0] = 1;
    
    // 标记马的控制点
    for (int i = 0; i < 9; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >=0 && ny >=0 && nx <=n && ny <=m)
            dp[nx][ny] = -1;
    }
    
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (dp[i][j] == -1) continue;
            if (i > 0 && dp[i-1][j] != -1) dp[i][j] += dp[i-1][j];
            if (j > 0 && dp[i][j-1] != -1) dp[i][j] += dp[i][j-1];
        }
    }
    cout << (dp[n][m] == -1 ? 0 : dp[n][m]);
    return 0;
}

Python版（记忆化递推）

n, m, x, y = map(int, input().split())
dp = [[0]*(m+1) for _ in range(n+1)]
dp[0][0] = 1
directions = [(0,0), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1)]

# 标记障碍
for dx, dy in directions:
    nx, ny = x + dx, y + dy
    if 0 <= nx <= n and 0 <= ny <= m:
        dp[nx][ny] = -1

for i in range(n+1):
    for j in range(m+1):
        if dp[i][j] == -1:
            continue
        if i > 0 and dp[i-1][j] != -1:
            dp[i][j] += dp[i-1][j]
        if j > 0 and dp[i][j-1] != -1:
            dp[i][j] += dp[i][j-1]
print(dp[n][m] if dp[n][m] != -1 else 0)

---

💡 动态规划四步心法

1. 定义状态：明确dp[i][j]的含义

2. 转移方程：找出状态间的关系式

3. 初始化：处理好边界条件

4. 遍历顺序：确保计算顺序正确

---

🔥 关注我，算法竞赛之路不再迷茫！