1. 该问题可以分解为多个子问题（阶段）
2. 具有最优化子结构-----无后效性------有重叠子问题 ===》 用动态规划
3. 可以计算每个step的最优解（必须包含本身数值），然后比较最后一个step和上一个step的值
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < len; i++){
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
return Math.min(dp[len - 1], dp[len - 2]);
}
}
D131 746. Min Cost Climbing Stairs 题目链接 746. Min Cost Cli...
746. Min Cost Climbing Stairs On a staircase, the i-th st...
Algorithm 746. Min Cost Climbing Stairs Review Tip B+树为何作...
Algorithm 746. Min Cost Climbing Stairs按tag刷题，这是一道典型的dp题目...
链接地址 解题思路 1. 该问题可以分解为多个子问题（阶段） 2. 具有最优化子结构-----无后效性------...
https://leetcode.com/problems/min-cost-climbing-stairs/de...
https://leetcode.com/problems/min-cost-climbing-stairs/ M...
原题地址 https://leetcode.com/problems/min-cost-climbing-stai...
DP解法：定义一个dp数组，dp[i]为到达第i层的最小花费，dp[i]仅与dp[i-1]和dp[i-2]和相应层...
题目描述 On a staircase, the i-th step has some non-negative ...
本文标题：746. Min Cost Climbing Stairs
本文链接：https://www.haomeiwen.com/subject/igoxmftx.html
网友评论