引入:斐波那契数列
递归版本:(太慢需要优化)
int f(int n) {
if (n == 0 || n == 1) return 1;
else return f(n - 1) + f(n - 2);
}
递推版本:
a[0] = a[1] = 1;
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
}
return a[n];
总结: 递归重复计算了一些东西\((\)例如算\(f[6]\)时算了\(f[4]\),算\(f[5]\)时又算了\(f[4])\)，重复子问题，导致算法效率低下。
解决方法:
- 空间换时间
- 已经计算过的记录下来避免重复计算
记忆化搜索版本：
int calc(int n) {
if (f[n] != 0) return f[n];
else return (f[n] = calc(n - 1) + calc(n - 2));
}
记忆化搜索
- 用数组等将已经算过的东西记录下来在下一次要使用的直接用已经算出的值，避免重复运算，去掉的重复的搜索树。
走楼梯问题
题目描述:
爬n阶的楼梯，一次可以爬1阶或2阶，问要爬完这n阶楼梯，共有多少种方法?
思考:
假设现在在第n阶楼梯上，显然上一步是在n-1阶或者n-2阶，根据分类加法原理知道，第n阶的方法=n-1阶的方法+n-2阶的方法
同样的，对于n-1阶和n-2阶用类似方法求解。
求到第1阶和第2阶时，显然方法数分别为1，2。
所以用\(f[i]\)表示爬到第i阶的方法数，那么
f[1] = 1, f[2] = 2;
f[i] = f[i-1]+f[i-2];
拓展：
若规定有\(m\)个第\(x_i\)级楼梯不能走。
解决方法：f[\(x_i\)] = 0,就相当于不能走。
爬蜂房(斐波那契变形)
题目描述:
一只蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
方法:
用f[i]表示从a爬到i的方案数
\(i < a,f[i] = 0;\)
\(i = a,f[i] = 1;\)
\(i > a,f[i] = f[i-1]+f[i-2];\)
一、动态规划概述
- 动态规划是解决多阶段决策过程最优化的一种方法。
- 最优化原理: 子问题的局部最优将导致整个问题的全局最优，即问题具有 最优子结构 的性质，也就是说一个问题的最优解只取决于其子问题的最优解