学习安排根据《代码随想录》
动态规划：Dynamic Programming，简称DP;
使用场合：
存在许多重叠子问题寻找最优解
使用特点：动规中每一个状态由上一个状态推到而来
动规五步：
先 确定 dp[i] 以及 i 的含义后 确定 递推公式【☆☆☆☆】再 dp[i]初始化【☆☆☆☆】再 确定遍历顺序【☆☆☆☆】最后 验证/打印dp[i] 【★★★】
动规问题没通过，检查思路：验证/打印dp[i] 查看是否和自己推导的一样：
- 一样：递推公式是否出错？ dp[i]初始化是否出错？ 遍历顺序是否出错？不一样：代码实现细节有误
动规与递归的关系？
答：动规是一种题型、算法，递归是一种调用方法，动规的问题包含递归的思路，还包含dp的初始化等，递归知识一种调用公式，不涉及调用的初始化。
动规与贪心的关系？
答：贪心是一种局部选优算法，会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，动规是先寻找子问题的最优解，然后再做选择。
以 leetcode 509 斐波拉契为例
动规五步：1.确定 dp数组 以及 i 的含义：
定义一个 dp[i]，这里 i 表示第i个数字 dp[i]表示 第 i个数对应的斐波拉契数值！
2. 确定 递推公式 ：
题目已给： dp[i]=dp[i-1]+dp[i-2];
3. 确定初始化：
题目已给： dp[0]=0;dp[0]=1
4.确定遍历顺序：
由递推公式知：第 i 项 依赖 前两项——即遍历的顺序是从前到后的！
5.举例验证 dp数组：
假设n=10，根据递推公式得到： 0 1 1 2 3 5 8 13 21 34 55
动态规划代码：
class Solution {
public:
void f(int n,vector&dp)
{
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
}
int fib(int n)
{
vectordp(n+1);
if(n<=1)return n;
else f(n,dp);
return dp[n];
}
};
递归代码：
class Solution {
public:
int fib(int n) //确定递归 函数的返回值 以及 参数类型
{
if(n<=1) return n;//确定 终止条件
int i=fib(n-1)+fib(n-2);// 确定前进段
return i;
}
};
为什么用i来接收？ 因为 fib 返回类型为 整型
写递归用 递归三步！！！
