织梦教育咨询企业网站模板厦门谷歌推广

理论基础

题型

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