动态规划

（1）重复子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果

通常不同的子问题个数随问题的大小呈多项式增长，用动态规划算法只需要多项式时间，从而获得较高的解题效率

（2）最优子结构

一个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质 分析问题的最优子结构性质：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 最优子结构是一个问题能用动态规划算法求解的前提 动态规划算法与分治算法的异同点：

（1）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题

（2）分治算法经分解得到的子问题往往是独立的

（3）动态规划算法经分解得到的子问题往往不是独立的，有些子问题被重复计算多次

1 是否为动态规划

1. 能否满足无后效性 2. 能否满足有最优解 3. 能否满足是重叠子

如 斐波那契数列

斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和

2定义状态变量

画图表 找关系

3写出状态转移方程

(1) 从哪里来： f[i]=f[i-1]+f[i-2]
(1) 到哪里去： f[i+1]=f[i]+f[i-1]

4边界

f[1]=1 f[2]=1

5代码实现

#include <bits/stdc++.h>
using namespace std;
int n,f[105];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

    cin>>n;
    
    //从哪来
    f[1]=f[2]=1;
    for(int i=3;i<=n;++i){
		f[i]=f[i-1]+f[i-2];
    }
    /*
    
    到哪去
    f[1]=1;
    for(int i=1;i<=n;++i){
        f[i+1]=f[i]+f[i-1];
    }
    
    */
    cout<<f[n];
	return 0;
}