东莞网站建设品牌公司,中国最好的建设网站,望野王绩朗诵,平湖网站建设流程今天有点事#xff0c;先做一题#xff0c;剩下的明天补。
509. 斐波那契数
这道题目太简单了#xff0c;递归几行代码就结束了#xff0c;用动态规划做也可以#xff0c;主要是学习一下动态规划五部曲。 这是递归的代码
class Solution {
public:int fib(int n) {//确…今天有点事先做一题剩下的明天补。
509. 斐波那契数
这道题目太简单了递归几行代码就结束了用动态规划做也可以主要是学习一下动态规划五部曲。 这是递归的代码
class Solution {
public:int fib(int n) {//确定终止条件if(n 0) return 0;if(n 1) return 1;return fib(n - 1) fib(n - 2); }
};这是动态规划的代码
class Solution {
public:int fib(int n) {//1.确定dp[i]的含义斐波那契数列第i个数的值//2.确定递推公式 dp[i] dp[i - 1] dp[i - 2]//3.dp数组初始化 dp[0] 0, dp[1] 1//4.确定遍历顺序从前往后遍历//5.打印数组(省略)if(n 2) return n;//大于等于2的情况vectorint dp(2);int sum;dp[0] 0;dp[1] 1;for(int i 2; i n; i){sum dp[0] dp[1];dp[0] dp[1];dp[1] sum;}return dp[1];}
};先这样。 70. 爬楼梯
这道题目之前做过印象非常深因为当时还没刷代码随想录第一次做这种动态规划题非常烧脑。而且就算搞明白这个本质上是斐波那契数列以后用递归也做不了因为递归会超时。。。。爬到第i个台阶的方法数取决于爬到第i-1和i-2阶的方法数之和就是纯纯的斐波那契数列啊。
class Solution {
public:int climbStairs(int n) {if(n 2) return n;vectorint dp(3);dp[1] 1;dp[2] 2;int sum;for(int i 3; i n; i){sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}};
746. 使用最小花费爬楼梯
这道题目没有看讲解自己AC的按照动态规划五部曲 1.确定dp[i]的含义爬到下标为i台阶所需的最小花费 2.确定递推公式 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]) 3.dp数组初始化 dp[0] 0, dp[1] 0 因为开局选择起点的时候不需要花钱 4.确定遍历顺序从前往后遍历 5.打印数组(省略) 这道题的核心就在于递推公式的构建不像之前两道题只是前两项相加那么简单这道题还需要求二者之间的最小值。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {//1.确定dp[i]的含义爬到下标为i台阶所需的最小花费//2.确定递推公式 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])//3.dp数组初始化 dp[0] 0, dp[1] 1//4.确定遍历顺序从前往后遍历//5.打印数组(省略)vectorint dp(cost.size() 1);dp[0] 0;dp[1] 0;int sum 0;//总花费为dp[cost.size()]for(int i 2; i cost.size(); i){sum min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);dp[i] sum;}return dp.back();}
};补完了享受周末~