Day11 动态规划入门
动态规划 就是 : 给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法.
记忆化搜索 = 暴力dfs + 记录答案
动态规划入门思路: dfs暴力 --- 记忆化搜索 --- 递推
1dfs > 2记忆化搜索 > 3逆序递推 > 4顺序递推 > 5优化空间 !
递归的过程:
"递" 的过程是: 分解子问题的过程;
"归" 的过程才是: 产生答案的过程;
"递" -- 自顶向下, "归" -- 自底向上 ， 其中 "底" 是 递归搜索树 的底
写出递推公式的方法:
递推 的公式 = dfs 向下 递归 的公式
递推 数组的初始值 = 递归 的边界
一.经典跳台阶
一个楼梯共有 nn 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 nn 级台阶一共有多少种方案。
输入格式
共一行，包含一个整数 nn。
输出格式
共一行，包含一个整数，表示方案数。
数据范围
1≤n≤15
#include<iostream>
using namespace std;
const int N = 20;
int n;
int f[N];
int main(){
scanf("%d",&n);
f[1] = 1, f[2] = 2;
if(n == 1 || n == 2){
printf("%d\n", f[n]);
return 0;
}
int newf = 0, temp1 = 1, temp2 = 2;
for(int i = 3; i <= n; i++){
newf = temp1 + temp2;
temp1 = temp2;
temp2 = newf;
}
for(int i = 3; i <= n; i++){
f[i] = f[i - 1] + f[i - 2];
}
printf("%d\n",f[n]);
return 0;
}