动态规划原理：从采药问题到最优决策的递推方法
采药问题为何是动态规划的经典案例？
考虑在限定时间内采集草药的问题：给定总时长和若干草药，每株草药有耗时和价值，目标是在不超过总时长前提下最大化总价值。例如当总时长为70分钟，草药A耗时71分钟（价值10），草药B耗时69分钟（价值1），草药C耗时1分钟（价值2）时，贪心算法（优先选价值最高）会失效——最优解是选择B和C（总价值3），而非单独选择高价值的A。
此问题本质是0-1背包模型，完美诠释动态规划（DP）核心思想：全局最优解由子问题最优解组合而成。
动态规划的核心机制
1. 记忆化：避免重复计算
暴力递归枚举所有组合（每株草药选/不选）在草药数量达30株时需计算约10亿次。动态规划通过重叠子问题识别，用DP数组存储子问题解。例如"前i株草药使用j分钟的最优解"会被多次计算，通过记忆化避免重复。
2. 最优子结构：决策的传递性
若"前i株草药使用j分钟"的最优解包含第i株草药，则"前i-1株草药使用j-ti分钟"的解必须最优。状态转移方程为：
maxValue[j] = max(不选当前草药, 当前草药价值 + maxValue[j - timeCost])逆序更新时长（从总时长向当前草药耗时遍历），确保每株草药仅选一次。
动态规划实现框架
1. 状态定义：问题维度建模
定义maxValue[time]表示特定时间内的最大价值。复杂问题可扩展为二维状态，如dp[i][j]（前i个物品在容量j下的最优解）。
2. 状态转移：递推关系构建
遍历每株草药，更新状态数组：
for (int time = totalTime; time >= herbTime; time--) {
maxValue[time] = max(maxValue[time],
maxValue[time - herbTime] + herbValue);
}新草药的加入基于历史状态修正最优解。
3. 初始化：设置基础状态
零时间价值为零（maxValue[0] = 0），其他状态初始化为最小值。需处理无效状态（如负时间）。
空间优化：降维策略
二维状态dp[i][j]（前i株草药j分钟的最优解）可压缩为一维数组。关键在逆序更新：正序会导致重复选择（完全背包问题），逆序保证maxValue[j-timeCost]未被当前草药修改。
应用场景与常见误区
适用问题：最优化目标（最大值/最小值）、子问题重叠（如路径规划）、状态依赖历史（如股票交易）。
典型错误：
- 混淆背包类型：0-1背包需逆序，完全背包需正序
- 边界条件缺失：未初始化
maxValue[0] = 0 - 过早优化：二维状态更易理解，应在正确性保证后压缩
示例代码实现：
#include <stdio.h>
#define MAX_TIME 1001
int main() {
int totalTime, herbCount;
int maxVal[MAX_TIME] = {0}; // 初始化零时间价值为0
scanf("%d %d", &totalTime, &herbCount);
for (int i = 0; i < herbCount; i++) {
int timeCost, herbValue;
scanf("%d %d", &timeCost, &herbValue);
for (int t = totalTime; t >= timeCost; t--) {
if (maxVal[t - timeCost] + herbValue > maxVal[t]) {
maxVal[t] = maxVal[t - timeCost] + herbValue;
}
}
}
printf("%d", maxVal[totalTime]); // 输出最终结果
return 0;
}