每天一道算法题【蓝桥杯】【使用最小花费爬楼梯】
思路
动态规划
状态表示
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]);//第一次跳可以选择跳到第一个台阶或第二个台阶
}
};