746. Min Cost Climbing Stairs

发布时间：2020-12-14 04:47:56 所属栏目：大数据来源：网络整理

导读：两种方法，核心思想都一样，求出走到每一步上的最小开销，直到最后一步和倒数第二步，比较其最小值返回即可。方法一，用一个辅助的容器 1 class Solution 2 { 3 public : 4 int minCostClimbingStairs(vector int cost) 5 { 6 int n= cost.size(); 7 vector

两种方法，核心思想都一样，求出走到每一步上的最小开销，直到最后一步和倒数第二步，比较其最小值返回即可。

方法一，用一个辅助的容器

 1 class Solution 
 2 {
 3 public:
 4     int minCostClimbingStairs(vector<int>& cost) 
 5     {
 6         int n=cost.size();
 7         vector<int> help(n);
 8         help[0]=cost[0];
 9         help[1]=cost[1];
10         for(int i=2;i<n;i++)
11             help[i]=cost[i]+min(help[i-2],help[i-1]);
12         return min(help[n-2],help[n-1]);
13     }
14 };

方法二，不用辅助容器，用两个辅助变量

 1 static int wing=[]()
 2 {
 3     std::ios::sync_with_stdio(false);
 4     cin.tie(NULL);
 5     return 0;
 6 }();
 7 
 8 class Solution 
 9 {
10 public:
11     int minCostClimbingStairs(vector<int>& cost) 
12     {
13         int sz=cost.size();
14         int left1=cost[0];
15         int left2=cost[1];
16         int cur=0;
17         for(int i=2;i<sz;i++)
18         {
19             cur=min(left1,left2)+cost[i];
20             left1=left2;
21             left2=cur;
22         }     
23         return min(left1,left2);
24     }
25 };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!