[数据结构与算法]算法题目——使用最小花费爬楼梯(动态规划)

题目链接：746.使用最小花费爬楼梯

方法:动态规划

假设数组cost的长度为n,则n个阶梯分别对应下标0到n- 1,楼层顶部对应下标n,问题等价于计算达到下标n的最小花费。可以通过动态规划求解。

创建长度为n + 1的数组dp,中dp[i] 表示达到下标i的最小花费。

于可以选择下标0或1作为初始阶梯，因此有dp[0] = dp[1]= 0。

当2≤i≤n时，可以从下标i-1使用cost[i- 1]的花费达到下标i,或者从下标i-2使用costli - 2]的花费达到下标i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如吓:

dp[i]= min(dp[i - 1] + costi- 1],dp[i- 2] + cost[i - 2])

依次计算dp中的每-项的值， 最终得到的dp[n]即为达到楼层顶部的最小花费。

#include<iostream>
#include<algorithm>

开通VIP 解锁文章