1. 动态规划概述

????????“动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”
????????通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。
????????同时，我们也可以对动态规划进行空间压缩，起到节省空间消耗的效果。

2. 题目类型

计数
- 有多少种方式走到右下角
- 有多少种方法选出k个数使和为sum
求最值
- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度
求存在性
- 取石子游戏，先手是否必胜
- 能不能选出K个数使得和为sum

3. 解题步骤

(1) 确定状态
- 简单的说，就是解动态规划时需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似解数学题中，xyz代表什么一样，具体分为下面两个步骤：
  - 研究最优策略的最后一步
  - 化为子问题
(2) 转移方程
- 根据子问题定义直接得到
(3) 初始条件和边界情况
- 初始条件一般都是f[0]、f[1]这种，多看看
- 边界条件主要是看数组的边界，数组越不越界
(4) 计算顺序
- 利用之前的计算结果
- 从左到右，从上到下
(5) 举例验证
- 按照转移方程来推导数组，观察是否与程序运行结果一样

注意事项：

数组范围的确定，用到n，数组大小就设为n+1，用不到数组大小就设置为n
dp[0]是否有意义

4. 案例1：斐波那契数列

【题目】斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n)

【分析】
（1）确定状态
用一维数组来保存递归结果，确定数组以及下标含义：f[i]定义为第i个数的斐波那契数值是f[i]

（2）转移方程
f[i] = f[i-1] + f[i-2]

（3）初始化以及边界条件
f[0] = 0;
f[1] = 1;

（4）确定遍历顺序
f[i]依赖于f[i-1]和f[i-2] ，故计算顺序是从左到右进行计算。

（5）举例验证
0 1 1 2 3 5 8 13 21 34 55

【C++】
时间复杂度：O(N)
空间复杂度：O(N)

int fib(int n){
	if(n < 2) return n;
	vector<int> f(n+1);//因为需要用到f[n]，故数组大小为n+1；
	f[0] = 0;
	f[1] = 1;
	for(int i = 2;i <= n;++1){
		f[i] = f[i-1] + f[i-2];
	}
	return f[n];
}

也可只维护两个数组，不需要记录整个数列
时间复杂度：O(N)
空间复杂度：O(1)

int fib(int n){
	if(n <= 1) return n;
	int f[2];
	f[0] = 0;
	f[1] = 1;
	for(int i = 2;i <= n;++1){
		int sum = f[0] + f[1];
		f[0] = f[1];
		f[1] = sum;
	}
	return f[1];
}

5. 案例二：爬楼梯

【题目】假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

【分析】
（1）确定状态
用一维数组来保存递归结果，确定数组以及下标含义：f[i]定义为爬到第i层，有f[i]种方法。

（2）转移方程
f[i] = f[i-1] + f[i-2]

（3）初始化以及边界条件
f[0] 无意义
f[1] = 1;
f[2] = 2;

（4）确定遍历顺序
f[i]依赖于f[i-1]和f[i-2] ，故计算顺序是从左到右进行计算。

（5）举例验证
1 2 3 5 8

【C++】
时间复杂度：O(N)
空间复杂度：O(N)

int climbStairs(int n ){
	if(n <= 1) return n;
	vector<int> f(n+1);
	f[1] = 1;
	f[2] = 2;
	for(int i = 3;i <= n;i++){
		f[i] = f[i-1] + f[i-2];
	}
	return f[n];
}

6. 案例三：使用最小花费爬楼梯

【题目】数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

【示例】

输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

【分析】
（1）确定状态
用一维数组来保存递归结果，确定数组以及下标含义：f[i]定义为爬到第i层的最少花费为f[i]。

（2）转移方程
f[i] = min{ f[i-1] , f[i-2] } + cost[i]

（3）初始化以及边界条件
vector f(cost.size());
f[0] = cost[0];
f[1] = cost[1];

（4）确定遍历顺序
f[i]依赖于f[i-1]和f[i-2] ，故计算顺序是从左到右进行计算。

（5）举例验证
cost = [1，100，1，1，1，100，1，1，100，1]
f[i] = [1，100，2，3，3，103，4，5，104，6]

【c++】
时间复杂度：O(N)
空间复杂度：O(N)

int minCostClimbStairs(vector<int>& cost){
	vector<int> f(cost.size());
	f[0] = cost[0];
	f[1] = cost[1];
	for(int i = 2;i < cost.size();++i){
		f[i] = min(f[i-1],f[i-2])+cost[i];
	}
	//最后一步不用花费，因为到倒数第一步和倒数第二步时，下一步即可登顶，故取两值之间的最小值
	return min(f[cost.size()-1],f[cost.size()-2]);
}