仿牌网站服务器,班级优化大师官网下载,响应式相册网站模板,网站如何做mip目录
动态规划理论基础
什么是动态规划
动态规划的解题步骤
动态规划的debug
509. 斐波那契数
前言
思路
算法实现
方法一#xff1a;动态规划
方法二#xff1a;递归法 70. 爬楼梯
前言
思路
算法实现
拓展
746. 使用最小花费爬楼梯
算法实现
总结 动态规划…目录
动态规划理论基础
什么是动态规划
动态规划的解题步骤
动态规划的debug
509. 斐波那契数
前言
思路
算法实现
方法一动态规划
方法二递归法 70. 爬楼梯
前言
思路
算法实现
拓展
746. 使用最小花费爬楼梯
算法实现
总结 动态规划理论基础
什么是动态规划 动态规划英文名为Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的。
动态规划的解题步骤 代码随想录中总结了动态规划的五部曲
确定dp数组以及下标的含义确定递推公式文章链接dp数组如何初始化确定遍历顺序举例推导dp数组。
动态规划的debug 写动规题目代码出问题很正常找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的 做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。 这样才是一个完整的思考过程而不是一旦代码出问题就毫无头绪的东改改西改改最后过不了或者说是稀里糊涂的过了。
509. 斐波那契数 题目链接 文章链接 前言 对于动规如果没有方法论的话可能简单题目可以顺手一写就过难一点就不知道如何下手了。从一开始做题就按照动态规划的五部曲顺序来执行。
思路 按照动态规划五部曲来执行
确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数列值是dp[i] 2.确定递推公式 题目中已经给出递推公式dp[i] dp[i - 1] dp[i - 2] 3.dp数组初始化 题目同样已经给出dp[0] 0, dp[1] 1; 4.确定遍历顺序 前序遍历 5.举例推导dp数组 按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列0 1 1 2 3 5 8 13 21 34 55 如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。
算法实现
方法一动态规划
class Solution {
public:int fib(int n) {if (n 1) return n;vectorint dp(n 1);dp[0] 0;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}; 本题的dp实现很简单因为题目信息已经给出递推公式和初始化值也可以只维护dp数组前两个值算法如下
class Solution {
public:int fib(int n) {if (n 1) return n;int dp[2];dp[0] 0;dp[1] 1;for (int i 2; i n; i) {int sum dp[0] dp[1];dp[0] dp[1];dp[1] sum;}return dp[1];}
};
方法二递归法 还可以使用递归法进行实现递归的实现较为简单递归终止条件就是当n小于2。
class Solution {
public:int fib(int n) {if (n 2) return n;return fib(n - 1) fib(n - 2);}
}; 70. 爬楼梯 题目链接 文章链接 前言 本题就没有像上一题一样直接给出递推公式我们先自自己举几个例子就可以发现规律。
思路 按照题目条件爬到第一层楼梯有一种方法爬到二层楼梯有两种方法。那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。 利用动态规划五部曲来进行分析
1.确定dp数组以及下标的含义 dp[i]的含义是爬到第i层楼梯有dp[i]种方法
2.确定递推公式 从dp[i]的定义可以看出dp[i] 可以有两个方向推出来一个是dp[i - 1]上i - 1层楼梯已经有dp[i - 1]种方法再跳一个台阶就是dp[i]另一个是dp[i - 2]上i - 2层楼梯已经有dp[i - 2]种方法那么再跳两个台阶就是dp[i]。因此dp[i]就是 dp[i - 1]与dp[i - 2]之和 所以dp[i] dp[i - 1] dp[i - 2] 。尤其注意在推导dp[i]的时候一定要时刻想着dp[i]的定义否则容易跑偏。这体现出确定dp数组以及下标的含义的重要性
3.dp数组初始化 需要注意的是题目中说了n是一个正整数题目根本就没说n有为0的情况。所以本题不需要讨论dp[0]的初始化直接初始化dp[1] 1dp[2] 2然后从i 3开始递推。
4.确定遍历顺序 从递推公式dp[i] dp[i - 1] dp[i - 2];中可以看出遍历顺序一定是从前向后遍历的
5.举例推导dp数组 同上题思路一致。
算法实现
class Solution {
public:int climbStairs(int n) {if (n 1) return n;vectorint dp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}; 同样也有简化算法只维护dp数组前面几个元素
class Solution {
public:int climbStairs(int n) {if (n 1) return n;int dp[3];dp[1] 1;dp[2] 2;for (int i 3; i n; i){int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};
拓展 一步一个台阶两个台阶三个台阶直到 m个台阶有多少种方法爬到n阶楼顶
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1, 0);dp[0] 1;for (int i 1; i n; i) {for (int j 1; j m; j) { if (i - j 0) dp[i] dp[i - j];}}return dp[n];}
};
746. 使用最小花费爬楼梯 题目链接 文章链接 算法实现
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size() 1);dp[0] 0;dp[1] 0;for (int i 2; i cost.size(); i) {dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
}; 简化之后
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int dp[2];dp[0] 0;dp[1] 0;for (int i 2; i cost.size(); i) {int dpi min(dp[0] cost[i - 2], dp[1] cost[i - 1]);dp[0] dp[1];dp[1] dpi;}return dp[1];}
};
总结 今天了解了动态规划的理论以及较简单题目的实现在练习过程中熟悉了动态规划五部曲的使用感觉非常实用
