想象你在玩一个贪吃蛇游戏，每次吃到食物后身体变长。现在要计算吃到第n个食物时的最大得分——如果每次都暴力枚举所有可能路径，时间复杂度会爆炸！这时候动态规划（Dynamic Programming, DP）就像给贪吃蛇装了GPS，用「记住历史」的方式避免重复计算，让你从超时秒切到轻松AC。
核心概念讲解
动态规划的核心思想是「最优子结构」和「无后效性」：
最优子结构：问题的最优解包含子问题的最优解（比如爬楼梯问题，爬到第n阶的最优解由n-1和n-2阶决定）。
无后效性：当前状态只与之前状态有关，与未来无关（比如背包问题，选了哪些物品不影响后续决策）。
记忆化搜索（Memoization）是DP的「暴力+备忘录」版本：
递归尝试所有可能路径（暴力）。
遇到重复子问题时直接查表返回结果（备忘录）。
文字示意图说明：
假设计算fib(5)时，先递归调用fib(4)和fib(3)；当再次需要fib(4)时，直接从缓存中读取结果而非重新计算。
C++代码示例（斐波那契数列）
#include <bits/stdc++.h>
using namespace std;
// dp数组，dp[i]表示第i项斐波那契数
vector<long long> dp(100, -1); // 使用long long防止溢出，初始化为-1表示未计算
long long fib(int n) {
if (n <= 1) return n; // 边界条件
if (dp[n] != -1) return dp[n]; // 已计算则直接返回
// 递归计算并缓存结果
dp[n] = fib(n-1) + fib(n-2);
return dp[n];
}
int main() {
cout << fib(50) << endl; // 输出12586269025（正确值）
return 0;
}
注释说明：
long long类型确保存储大整数（如第50项斐波那契数）。-1作为未计算的标记，需与合法值区分。每个子问题仅计算一次，时间复杂度O(n)。
算法分析
时间复杂度：O(n)（每个子问题只计算一次）。
空间复杂度：O(n)（需存储dp数组）。
适用场景：有重叠子问题和最优子结构的问题（如背包、最长公共子序列等）。
局限性：若问题无重叠子问题（如简单排序），记忆化搜索效率低于普通递归。
注意事项
数据范围：注意数值溢出（如本题必须用
long long）。初始化：明确所有边界条件的初始值（如
dp[0]=0,dp[1]=1）。递归深度：对于大规模输入，可能触发栈溢出，可改用迭代法。
经典例题解析
洛谷 P1027 [NOIP2001 普及组] 数的划分
题意：将正整数n划分为若干正整数之和，求划分方案数（顺序不同视为相同）。
状态定义：
dp[i][j]表示将整数j划分为最大部分不超过i的划分数。递推式：
$$dp[i][j] = dp[i-1][j] + dp[i][j-i]$$
第一项：不选i，最大部分不超过i-1。
第二项：选至少一个i，剩余部分仍不超过i。
边界条件：
dp[i][0] = 1（空划分算一种方案）。j < i时，dp[i][j] = dp[i-1][j]（无法选i）。
完整代码示例：
#include <iostream>
using namespace std;
const int N = 100;
int dp[N][N];
int main() {
int n;
cin >> n;
for (int i = 0; i <= n; ++i) dp[i][0] = 1; // 初始化
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = (j >= i ? dp[i][j-i] : 0) + dp[i-1][j];
cout << dp[n][n] << endl;
return 0;
}
推荐练习
提示：考察01背包变形，注意物品重量与价值的对应关系。
提示：排列计数DP，需预处理阶乘逆元模运算。
提示：记忆化搜索+模运算，统计满足条件的子序列数量。
小结
记忆化搜索通过「空间换时间」优雅地解决重叠子问题，是理解DP的重要起点。下期我们将深入「递推式DP」，教你如何用迭代代替递归，进一步优化常数！