建设银行常熟支行网站,微赞直播平台,网站建设方案免费下载,临沂专业做网站一:题目 二:上码
class Solution {
public:/**思路:1.分析题意给出的数组的下标代表楼梯的台阶数2.动态规划五步走1:确定dp数组以及下标的含义dp[i]:表示到达第i层所需要花费的体力2:确定dp数组的递推公式那么如何得到dp[i](花费的体力)呢#xff1f;dp[i]由dp[i-1]或…一:题目 二:上码
class Solution {
public:/**思路:1.分析题意给出的数组的下标代表楼梯的台阶数2.动态规划五步走1:确定dp数组以及下标的含义dp[i]:表示到达第i层所需要花费的体力2:确定dp数组的递推公式那么如何得到dp[i](花费的体力)呢dp[i]由dp[i-1]或者dp[i-2]可以得到但是我们需要在其中选取一个小的dp[i] min(dp[i-1],dp[i-2]) cost[i];为甚要加上cost[i],题目中给出了,我们每到一个台阶的话,需要支付cost[i]才能继续向上爬3:确定dp数组的初始化cost.size() 2那么的话,可以直接一步到楼顶(那就不用花费)也可以从0开始dp[0] cost[0],然后再来一步到达楼顶 那就直接返回dp[0]和dp[1]中比较小的那个 (如果这个size() 2) cost.size() 2dp[0] cost[0];dp[1] cost[1];4:确定dp数组的遍历顺序这个肯定也是需要从前往后遍历,因为我们需要前面花费的体力5:举例验证cost [10,15,2,10]dp[3] min(dp[2],dp[1]) (这里不用加上cost[3],因为最后一步就直接登顶了)dp[2] min(dp[1],dp[0]) cost[2]; **/int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorintdp(n1);dp[0] cost[0];dp[1] cost[1];if(n 2) return min(dp[0],dp[1]);for(int i 2; i n; i) {if(i n){//最后一步是直接到达楼顶的不需要计算楼顶那层的自己的费用dp[i] min(dp[i-1],dp[i-2]);}else{dp[i] min(dp[i-1],dp[i-2]) cost[i];}}return dp[n];}
};
