思路
动态规划
状态表示
dp[i] 表示从第i个台阶开始跳跳到台阶顶使用的最小花费
状态转移方程
前一个台阶的最小花费要看后两个台阶来决定
dp[i]为后两个台阶花费的最小值加上这个台阶的花费
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]
初始化
dp[n - 1] = cost[n - 1];//第n-1个台阶跳到台阶顶的最小花费为cost[i-1]
dp[n - 2] = cost[n - 2];//第n-2个台阶跳到台阶顶的最小花费为cost[i-2]
注意返回值
return min(dp[0], dp[1]);//第一次跳可以选择跳到第一个台阶或第二个台阶
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits.h>
#include<vector>
using namespace std;
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int>dp(n);dp[n - 1] = cost[n - 1];//第n-1个台阶跳到台阶顶的最小花费为cost[i-1]dp[n - 2] = cost[n - 2];//第n-2个台阶跳到台阶顶的最小花费为cost[i-2]for (int i = n - 3; i >= 0; i--){dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];//前一个台阶的最小花费要看后两个台阶来决定//写出状态转移方程}return min(dp[0], dp[1]);//第一次跳可以选择跳到第一个台阶或第二个台阶}
};
)
