Description Link to heading
Solution Link to heading
It’s like 70.climbing-stairs plus, the recursive relationship becomes more complicated, but the essence is the same.
$$dp_n = \min[dp_{n - 1} + cost[i - 1], a_{n - 2} + cost[i - 2]]$$
After get the recursive relationship, we can write traversal code to get the answer using for loop.
Code Link to heading
#include <vector>
using std::vector;
class Solution {
public:
int minCostClimbingStairs(vector<int> &cost) {
int sz = cost.size();
vector<int> dp(2);
dp[0] = dp[1] = 0;
// dp[2] = cost[0] < cost[1] ? cost[0] : cost[1];
for (int i = 2; i <= sz; i++) {
// Original, space: O(n)
// dp[i] = (dp[i - 2] + cost[i - 2]) < (dp[i - 1] + cost[i - 1]) ? (dp[i - 2] + cost[i - 2]) : (dp[i - 1] + cost[i - 1]);
// Space optimized:
int res = dp[0] + cost[i - 2] < dp[1] + cost[i - 1] ? dp[0] + cost[i - 2] : dp[1] + cost[i - 1];
dp[0] = dp[1];
dp[1] = res;
}
return dp[1];
}
};