[代码随想录Day32打卡] 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

理论基础

题型

1. 动归基础（这一节就是基础题）
2. 背包问题
3. 打家劫舍
4. 股票问题
5. 子序列问题

动态规划五部曲

1. 确定dp数组及其下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印dp数组

509. 斐波那契数

简单~

1. 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数组

当前位置的值只与该位置的前两个数值有关，只需要维护长度为2的数组。

class Solution {
public:int fib(int n) {if(n==0 || n==1) return n;vector<int> dp(2);dp[0] = 0; dp[1] = 1;for(int i=2; i<=n; i++){int sum = dp[1] + dp[0];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

class Solution {public int fib(int n) {if(n == 0 || n == 1) return n;int[] dp = new int[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];}
}

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n == 0 or n == 1:return ndp = [0,1]for i in range(2, n+1):sum_ = dp[0] + dp[1]dp[0] = dp[1]dp[1] = sum_return dp[1] 

参考文章

1. https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

70. 爬楼梯

要明白如果爬n层有两种情况： 一种是从n-2层迈两步上来的，一种是从n-1层迈一步上来的。所以到达第n层的方法数量=到达第n-2层的方法数+到达第n-1层的方法数。

1. dp数组及其下标含义 dp[i] 表示到达第i层的方法数量
2. 递推公式 dp[i] = dp[i-1] + dp[i-2]
3. dp数组初始化 dp[1] = 1 dp[2] = 2，0没有实际意义
4. 遍历顺序：从前往后
5. 打印dp数组

当前位置数值只与当前位置前2个位置数值有关，只需要维护长度为2的数组，但是0没有实际意义，为了实现更加明确的初始化我们定义长度为3的数组，0这个位置不进行初始化。

class Solution {
public:int climbStairs(int n) {if(n==1 || n==2) return n;vector<int> dp(3);dp[1] = 1;//空出0来因为没有意义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];}
};

class Solution {public int climbStairs(int n) {if(n == 1 || n == 2) return n;int[] dp = new int[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];}
}

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n == 1 or n == 2:return ndp = [None, 1, 2]for i in range(3, n+1):sum_ = dp[1] + dp[2]dp[1] = dp[2]dp[2] = sum_return dp[2]

参考文章

1. https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

746. 使用最小花费爬楼梯

Note：注意题目描述，该位置不花费体力，往上跳花费体力。并且cost的长度是顶楼。

1. dp数组及其下标含义：dp[i] 到达第i层所需要的最小花费为dp[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;//因为当前位置不花费，向上跳才花费所以都初始化为0
4. 遍历顺序：从前往后
5. 打印dp数组

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {if(cost.size()<2) return 0;vector<int> dp(2);for(int i = 2; i <= cost.size(); i++){int minCost = min(dp[0] + cost[i-2], dp[1] + cost[i-1]);dp[0] = dp[1];dp[1] = minCost;}return dp[1];}
};

class Solution {public int minCostClimbingStairs(int[] cost) {if(cost.length<2) return 0;int[] dp = new int[]{0, 0};for(int i = 2; i <= cost.length; i++){int minCost = Math.min(dp[0] + cost[i-2], dp[1] + cost[i-1]);dp[0] = dp[1];dp[1] = minCost;}return dp[1];}
}

class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""if len(cost)<2:return 0dp = [0, 0]for i in range(2, len(cost)+1):minCost = min(dp[0]+cost[i-2], dp[1]+cost[i-1])dp[0] = dp[1]dp[1] = minCostreturn dp[1]

参考文章

1. https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html