题解 | #最小花费爬楼梯#

用动态规划，首先确定公式，显然如果假设当前层下标为i，那么只可能从i-1和i-2而来；

那么截止到i层的最小花费为min(dp[i-1]+costs[i-1],dp[i-2]+costs[i-2]); 然后直接开摆，公式就是这么简单

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型vector * @return int整型 / / int costs(vector& cost,int index){ //下标从0开始 int val; if(index==0 or index==1) return cost[index]; if(index==cost.size()) val=0; else val=cost[index]; return min(val+costs(cost,index-1),val+costs(cost,index-2)); }*/ //递归废了，虽然思路更清晰；动态规划思路反人类，哈哈 //dp[0]=dp[1]=0,初始条件，表示跳到0和1不需要花费 //i从下标2开始，dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); int costs(vector& cost){ int max_index=cost.size(); int dp[max_index+1]; dp[0]=0;dp[1]=0; for(int i=2;i<=cost.size();i++){ dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.size()]; } int minCostClimbingStairs(vector& cost) { // write code here int size=cost.size(); int money=costs(cost); return money; } };