【代码随想录】刷题笔记Day40

本文主要是介绍【代码随想录】刷题笔记Day40，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

• 终于把贪心这一章刷完了，接下来动态规划！好多题啊，争取一两周搞定！

动态规划理论基础

• 动规做题五部曲
• 

509. 斐波那契数 - 力扣（LeetCode）

• 入门简单，状态转移方程：dp[i] = dp[i - 1] + dp[i - 2];

• class Solution {
  public:int fib(int N) {if (N <= 1) return N;vector<int> 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];}
  };

 70. 爬楼梯 - 力扣（LeetCode）

• 爬n阶可以由（n-1阶爬1阶 n-2阶爬2阶）组成，所以方式 dp[i] = dp[i - 1] + dp[i - 2]

• class Solution {
  public:int climbStairs(int n) {if(n == 1) return 1;  // dp[1] = 1int dp[46];dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
  };

 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

• 有花费的爬楼梯，dp[i]表示爬到第i阶所需要的最小花费，转移条件dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);，初始化dp[0]和dp[1]为1
• 

• class Solution {
  public:int minCostClimbingStairs(vector<int>& cost) {int dp[1001];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()];}
  };

后言

•  上午先写这么多，上课实在效率太低，感觉动规的分析还挺好玩（数学归纳？）

这篇关于【代码随想录】刷题笔记Day40的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---