動態規劃?就是 : 給定一個問題，我們把它拆成一個個子問題，直到子問題可以直接解決。然后把子問題的答案保存起來，以減少重復計算。再根據子問題答案反推，得出原問題解的一種方法.

記憶化搜索 = 暴力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;
}