使用最小花费爬楼梯题解集合
- 递归
- 动态规划
- 动态规划优化---状态压缩
递归
思路:
将问题转化为对二叉树的遍历，因为初始阶段可以选择0或1，因此会有两颗二叉树，那么最终结果取这两颗二叉树中较小值
代码:
代码语言：javascript复制class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
//第一个元素必选，因此我们从第二个元素开始判断
return min(dfs(cost, 1,true) cost[0], dfs(cost, 2,true) cost[1]);
}
int dfs(vector<int>& cost,int index,bool isSel)//isSel记录当前位置选了还是没选
{
if (index == cost.size()) return 0;
//上面一层是否选了
if (isSel)
//上面一层选了，那么当前层可以选也可以不选
return min(dfs(cost, index 1, true) cost[index], dfs(cost, index 1, false));
//上面一层没选，当前层必须要选
return dfs(cost, index 1, true) cost[index];
}
};
动态规划
理解题意:
只有从当前台阶准备往上面继续跨台阶的时候，才需要加上跨当前台阶的费用
1.dp[i]的含义
到达当前第i级台阶，需要的最小花费为dp[i]
2.状态转移方程
dp[i]=min(dp[i-1] cost[i-1],dp[i-2] cost[i-2])
因为跨上第i级台阶的前，我们可能处于第i-1级台阶，也可能处于第i-2级台阶，当我们处于第i-1级台阶的时候，我们只需要跨一步，就可以到达第i级台阶，花费为dp[i-1] cost[i-1]。
当我们处于第i-2级台阶的时候，我们需要跨两步到达第i级台阶，花费为dp[i-2] cost[i-2]
那么对于第i级台阶来说，有两种方式可以到达，我们需要从中挑选中花费最少的一种，即dp[i]=min(dp[i-1] cost[i-1],dp[i-2] cost[i-2])
3.初始化条件
从dp[i-1]和dp[i-2]可以推导出，初始化条件为dp[0]和dp[1].
dp[0]=0;
dp[1]=0;
这里dp[0]，表示当我们位于0级台阶，即位于地面时。
代码:
代码语言：javascript复制class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
vector<int> dp(cost.size() 1, 0);
//只有从当前台阶准备往上面继续跨台阶的时候，才需要加上跨当前台阶的费用
for (int i = 2; i <=cost.size(); i )
{
dp[i] = min(dp[i - 1] cost[i-1], dp[i - 2] cost[i-2]);
}
return dp[cost.size()];
}
};
动态规划优化—状态压缩
从状态转移方程我们可以看出，计算当前位置的dp[i[，只和dp[i-1]和dp[i-2]有关，因此我们只需要记住dp[i].dp[i-1]和dp[i-2]这三个变量即可，即完成对空间和时间的双重压缩。
这里我们用三个变量dp0,dp1,dp2来分别记录对应的三个状态。
代码:
代码语言：javascript复制class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int dp0 = 0, dp1 = 0;
for (int i = 2; i <= cost.size(); i )
{
//每一次往后推一位，更新一个新元素的值
int dp2 = min(dp0 cost[i - 2], dp1 cost[i - 1]);
dp0 = dp1;
dp1 = dp2;
}
return dp1;
}
};
