aspcms网站地图,做网站是用ps还是ai,百度免费网站怎样建设,做宣传网站需要多少钱● 理论基础
DP大约五种问题#xff1a;
动规基础#xff08;斐波那契数列、爬楼梯#xff09;#xff1b;背包问题#xff1b;股票问题#xff1b;打家劫舍#xff1b;子序列问题。
要搞清楚#xff1a;
DP数组及其下标的含义#xff1b;DP数组如何初始化#x…● 理论基础
DP大约五种问题
动规基础斐波那契数列、爬楼梯背包问题股票问题打家劫舍子序列问题。
要搞清楚
DP数组及其下标的含义DP数组如何初始化递推公式遍历顺序打印DP数组
无论难易动态规划都可以用这5步来深入理解即动规五部曲。因为对于动规如果没有方法论的话可能简单题目可以顺手一写就过难一点就不知道如何下手了。
● 509. 斐波那契数
简单题也养成五部曲的习惯。
DP数组及其下标的含义dp[i]是第i个斐波那契数。
DP数组如何初始化dp[0]0;dp[1]1、递推公式dp[i]dp[i-1]dp[i-2]、遍历顺序一层for循环是从小到大递推所以从小到大遍历、打印DP数组设置n为一个不太大的数打印序列来检查正确性这些都是直接能知道的。
代码如下注意是返回dp[n]不是dp[n-1]所以一开始数组大小得是n1个。
class Solution {
public:int fib(int n) {if(n0)return 0;vectorint dp(n1);dp[0]0;dp[1]1;for(int i2;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
};
● 70. 爬楼梯
n1,2,3,4的方法数依次是1,2,3,5全是1步1种一个2步3种2个2步1种找规律发现还是一个斐波那契额数列。所以五部曲跟上一题相同。注意dp数组初始化的元素个数和返回的下标。
class Solution {
public:int climbStairs(int n) {if(n1)return 1;vectorint dp(n);dp[0]1;dp[1]2;//初始化,下标0是n1for(int i2;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n-1];}
};
● 746. 使用最小花费爬楼梯
五部曲
DP数组及其下标的含义dp[i]是从底部注意从0/从1开始都可以到第i层的最低花费。要返回的还是dp数组最后一个数dp[n]。DP数组如何初始化dp[0]0,dp[1]0也是0因为可以从1开始递推公式递推公式是要从之前的dp序列得到dp[i]所以我们要立足下标i根据题目意思要想到达i有两种选择上一节台阶跨一步上上一节台阶跨两步。取决于两种情况哪一种花费更低所以用mindp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])。遍历顺序仍然是从小到大打印DP数组
发现数组下标含义、初始化、递推都是要仔细思考的要做到一致统一。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {if(cost.size()1)return cost[0];int ncost.size();vectorint dp(n1);dp[0]0;//初始化dp[1]0;for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);coutdp[i] ;//打印检查}return dp[n];//底部到n个台阶的时间}
};
