动态规划（DP）
DP问题特征
特征：重叠子问题、最优子结构、无后效性
- 重叠子问题：计算大问题需要重复计算小问题，DP可以避免重复计算，代价是消耗更多的空间
- 最优子结构：大问题的最优解包含小问题的最优解，小问题的最优解可以推出大问题的最优解
- 无后效性：不关心子问题的过程，只关心子问题的结果
以斐波那契数列为例
斐波那契数列递推公式：\(fib(n) = fib(n - 1) + fib( n - 2)\)
- 递归
int fib(int n)
{
if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
时间复杂度为\(O(n^2)\)
- 自顶向下与记忆化
int mem[N];
int fib(int n)
{
if (n == 1 || n == 2) return 1;
if (mem[n]) return mem[n];
return mem[n] = fib(n - 1) + fib(n - 2);
}
时间复杂度为\(O(n)\)
- 自底向上制表递推
int dp[N];
int fib(int n)
{
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i ++ ) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
时间复杂度为\(O(n)\)
标签：return,int,笔记,fib,mem,初识,最优,DP From： https://www.cnblogs.com/Panmaru/p/17051526.html