要搞清楚#xff1a;

DP数组及其下标的含义#xff1b;DP数组如何初始化#x…●

理论基础

动规基础斐波那契数列、爬楼梯背包问题股票问题打家劫舍子序列问题。

要搞清楚

DP数组及其下标的含义DP数组如何初始化递推公式遍历顺序打印DP数组

无论难易动态规划都可以用这5步来深入理解即动规五部曲。

因为对于动规如果没有方法论的话可能简单题目可以顺手一写就过难一点就不知道如何下手了。

509.

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

i2;in;i){dp[i]dp[i-1]dp[i-2];}return

dp[n];}

n1,2,3,4的方法数依次是1,2,3,5全是1步1种一个2步3种2个2步1种找规律发现还是一个斐波那契额数列。

所以五部曲跟上一题相同。

注意dp数组初始化的元素个数和返回的下标。

class

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];}

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

minCostClimbingStairs(vectorint

cost)

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