LeetCode - 746. Min Cost Climbing Stairs [단순 dp]
2496 단어 dp 시작
746. Min Cost Climbing Stairs My SubmissionsBack to Contest
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost will have a length in the range [2, 1000]. Every cost[i] will be an integer in the range [0, 999].
제목: 몇 수를 드리자면 계단마다 걸어가는 대가를 의미합니다. 한 번에 한 걸음 두 걸음 걸어서 옥상에 올라가면 최소한의 소모 대가를 물어볼 수 있습니다.
분석: 방정식 dp[i]를 옮기는 것은 i단계 계단까지 가는 데 필요한 최소한의 대가를 의미한다. 옥상에 가야 하기 때문에'옥상'을 하나 더 넣어야 한다. 대가는 0이다. 옮기는 방정식은 dp[i]=min(dp[i-1]+cost[i], dp[i-1]+cost[i])이다.
참조 함수
class Solution {
public:
int dp[1010];
int minCostClimbingStairs(vector<int>& cost) {
if(cost.size() == 0) return 0;
cost.push_back(0);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2;i <= cost.size();i++) {
dp[i] = min(dp[i-1] + cost[i],dp[i-2]+cost[i]);
}
return dp[cost.size()];
}
};4
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode - 746. Min Cost Climbing Stairs [단순 dp]Min Cost Climbing Stairs My SubmissionsBack to Contest On a staircase, the i-th step has some non-negative cost cost[i] ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
