蓝桥杯快到了，很多小伙伴私信小编，想让我介绍一些基础的算法，那么今天它来了！
动态规划是一种通过将复杂问题分解为重叠子问题，并记录子问题解来避免重复计算的方法。其核心是状态定义和状态转移方程。在竞赛中，DP常用于解决最优化问题（如最大值、最小值）或计数问题（如路径总数）。典型的应用场景包括背包问题、最长子序列、路径规划等。
洛谷题目推荐：P1048 [NOIP2005 普及组] 采药
题目链接：P1048 采药
题目大意：有 T 秒时间采药，药田中有 M 株草药，每株草药需要 t[i] 秒采摘，价值为 w[i]。求在规定时间内能采到的草药最大总价值。
题目分析
-
问题转化：经典的 01背包问题。将时间视为背包容量，草药视为物品，目标是选出物品使得总重量不超过容量且总价值最大。
-
状态定义：定义
dp[j]表示使用j秒时间能获得的最大价值。 -
状态转移：对每株草药
i，从后向前遍历时间j（避免重复选取）：dp[j] = max(dp[j], dp[j - t[i]] + w[i]); -
初始化：
dp数组初始化为 0，表示未选择任何草药时的价值为 0。
关键代码解读（C++）
#include <bits/stdc++.h>
using namespace std;const int MAXT = 1005;
int dp[MAXT]; // dp[j]: 使用j秒的最大价值
int t[105], w[105]; // 每株草药的时间和价值int main() {int T, M;cin >> T >> M;for (int i = 1; i <= M; i++) {cin >> t[i] >> w[i];}// 动态规划核心for (int i = 1; i <= M; i++) { // 遍历所有草药for (int j = T; j >= t[i]; j--) { // 倒序更新，防止重复选取dp[j] = max(dp[j], dp[j - t[i]] + w[i]);}}cout << dp[T] << endl; // 输出最大价值return 0;
}
代码解析：
-
输入处理：读取总时间
T和草药数量M，存储每株草药的时间和价值。 -
动态规划过程：
-
外层循环：遍历每株草药，逐个考虑是否选择。
-
内层循环：从
T倒序遍历到t[i]，确保每个草药最多被选一次。 -
状态转移：
dp[j]取“不选当前草药”和“选当前草药”中的最大值。
-
-
输出结果：
dp[T]即为在T秒内能获得的最大价值。
注意事项
-
倒序遍历的意义：正序遍历会导致同一株草药被重复选取（完全背包问题），倒序保证每个物品只选一次。
-
空间优化：使用一维数组代替二维数组，降低空间复杂度至
O(T)。 -
边界条件：当
j < t[i]时无法选择当前草药，直接跳过。
扩展思考
动态规划的难点在于如何定义状态和找到状态转移方程。本题中，背包容量（时间）和物品价值（草药）的模型非常典型，类似的问题可以抽象为“资源分配”问题。例如：
-
资金预算分配（最大利润）
-
时间安排（最多任务数）
-
容器装载（最大利用率）
通过练习类似题目（如洛谷 P1060 [NOIP2006 普及组] 开心的金明），可以进一步掌握一维背包问题的变种。
