数据结构第九章-动态规划
什么是动态规划
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法，它来自于美国数学家R.E.Bellaman 等人提出的最优化原理，利用各阶段之间的关系，逐个求解，最终求得全局最优解 ，在设计算法时候，需要确认原问题与子问题，动态规划状态，边界状态结值，状态转移方程等关键要素
爬楼梯
#easy 70. 爬楼梯 - 力扣（LeetCode） 在爬楼梯时候，每次可以向上走1阶台阶或者2阶台阶，n阶楼梯有多少种上楼的方式？ 示例
示例 1：
输入：n = 2
输出：2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
方法1：暴力搜索（回溯）
每次只有两种操作（走一层或者两层），面临两种结果，只需要把两种结果对应的情况分别进行递归并相加即可
或者你当成二叉树看，左子树是-1，右子树是-2
代码如下
class Solution {
public:
int climbStairs(int n) {
if(n == 1||n ==2 ){
return n;//递归的返回条件，n=1的时候有1种走法n=2有两种方法
}
return climbStairs(n-1)+climbStairs(n-2);//递归执行，减小判断的数量
}
};
方法2： 动态规划
动态规划的原理
算法思路
因为每次最多只能爬2阶，楼梯的第i阶，只可能从第i-1阶和第i-2阶到达，故到达第i阶有多少种爬法，只与第i-1阶和第i-2阶的爬法数量直接相关
也就是说：要么从i-2阶一次爬两级到达i，要么从i-1爬一层到达i。虽然可以从i-2到i-1在到i，但是这种情况实际是包含在i-1到i的情况里面的，因为本质上来讲还是用这样的方法先到达了i-1层，然后再从i-1到达
代码实现如下
class Solution {
public:
int climbStairs(int n) {
std::vector<int> dp(n + 3, 0);//初始化dp数组
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++){//循环对第i阶进行计算
dp[i] = dp[i-1] + dp[i-2];//状态转移方程：第i阶的数量相当于第i-1阶的方法数量加上i-2阶的方法数量
}
return dp[n];
}
};
打家劫舍
#easy 198. 打家劫舍 - 力扣（LeetCode） 在一条直线上，有n个房屋，每一个房屋有着数量不等的财报，有一个盗贼希望从房屋中盗取财宝，由于房屋里面有报警器，如果同时从相邻的两个房屋中盗取财宝就会触发报警器，问在不触发报警器的情况下，最多可以获取多少财宝？
示例：
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
贪心算法必然不可行
比如[5,7,6] 在这种情况下，按照贪心算法来处理得到的结果是7，但是真正答案应该为11
动态规划
如果第i-1个房间被选择，那么第i个房间不能被选择，反之，如果第i个房间被选择，那么第i-1个房间不能被选择
解决方法如下
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0){
return 0;//判空
}
if(nums.size()==1){//如果nums只有一个元素
return nums[0];
}
//设置第i个房间的最优解为dp[i]
std::vector<int> dp(nums.size(),0);
dp[0] = nums[0];
dp[1] = std::max(nums[0],nums[1]);
for(int i = 2;i<nums.size();i++){
dp[i] = std::max(dp[i-2]+nums[i],dp[i-1]);//计算第I个房间的最优解,当选择第i个房间为最优解的时候，dp的值应该为第i-2个房间加上本房间，不选择的时候本房间的dp就是上一个房间的dp
}
return dp[nums.size()-1];
}
};
最大字段和
#hard 53. 最大子数组和 - 力扣（LeetCode） 给定一个数组，求这个数组的连续子数组，最大的一段的和
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
如果进行暴力枚举的话时间复杂度是O($n^2$)
动态规划
把前i个数字的最大字段和当成dp值
在上面的例子中，dp[4] 不能与之前的dp形成关系
以第i个数字为结尾的最大字段和为dp值
解决方法如下
class Solution {
public:
int maxSubArray(vector<int>& nums) {
std::vector<int> dp(nums.size(),0);//dp数组
dp[0] = nums[0];//dp0就是nums0
int max_res = dp[0];//初始化最大值
for(int i = 1;i<nums.size();i++){
dp[i] = std::max(dp[i-1]+nums[i],nums[i]);//状态转换方程
if(max_res<dp[i]){
max_res = dp[i];//记录最大值
}
}
return max_res
}
};
一般来说，当设计算法出现问题的时候，（比如只能想到枚举的算法），可以想想贪心和dp
找零钱
#medium 322. 零钱兑换 - 力扣（LeetCode） 本题是[[第三章：贪心算法#预备知识：贪心法，钞票支付问题|钞票支付问题]]的复杂版 在本题中由于钞票面值不一定是倍数关系，不能使用贪心算法 已知不同面值的钞票，求如何用最少数量的钞票组成某个金额，求可以使用的最少的钞票数量，如果任意数量的已知面值钞票都无法组成该金额，则返回-1
示例 1：
输入：coins = `[1, 2, 5]`, amount = `11`
输出：`3`
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = `[2]`, amount = `3`
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
贪心？
动态规划
边界条件就是dp[coins[i]]
解决方法如下
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
std:vector<int> dp;
//初始化dp数组
for(int i = 0;i<=amount;i++){//创建一个amout + 1的dp（包括0）
dp.push_back(-1);//所有值都为-1
}
dp[0] = 0;//金额0的最优解为0
for(int i = 1;i <= amount;i++){//递推
for(int j = 0; j < coins.size();j++){//循环各个面值，找到dp[i]的最优解
if(i - coins[j] >= 0 && dp[i-coins[j]]!= -1 ){//当前的金额能够包含在面值里面，而且
if(dp[i] == -1||dp[i] > dp[i - coins[j]] + 1){//当该点等于-1或者该点并不是最小值
dp[i] = dp[i - coins[j]] + 1;//递推公式
}
}
}
}
return dp[amount];
}
};
