鏈接: 使用最小花費(fèi)爬樓梯
題目描述
算法流程(方法一)
編程代碼
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
size_t size = cost.size() + 1;
vector<int> dp(size);
dp[0] = dp[1] = 0;
for(int i = 2;i < size;++i)
{
dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
}
return dp[size-1];
}
};
優(yōu)化代碼
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
size_t size = cost.size() + 1;
int a,b,c,d;
a = b = 0;
for(int i = 2;i < size;++i)
{
c = min(a+cost[i-2],b+cost[i-1]);
a = b;
b = c;
}
return c;
}
};
算法流程（方法二）
文章來源：http://www.zghlxwxcb.cn/news/detail-618653.html
編程代碼
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
size_t n = cost.size();
vector<int>vv(n);
vv[n-1] = cost[n-1];
vv[n-2] = cost[n-2];
for(int i = n-3;i >= 0;--i)
{
vv[i] = min(vv[i+1],vv[i+2])+cost[i];
}
return min(vv[0],vv[1]);
}
};
文章來源地址http://www.zghlxwxcb.cn/news/detail-618653.html
代碼優(yōu)化
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
size_t n = cost.size();
int a = cost[n-1];
int b = cost[n-2];
int c;
for(int i = n-3;i >= 0;--i)
{
c = min(a,b)+cost[i];
a = b;
b = c;
}
return min(a,b);
}
};
到了這里，關(guān)于LeetCode使用最小花費(fèi)爬樓梯（動(dòng)態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
