衡东网站制作,做网站哪家南京做网站,表单标签wordpress,外贸网站优化方案问题#xff1a;Leetcode 746. 使用最小花费爬楼梯
给你一个整数数组 cost #xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用#xff0c;即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你…问题Leetcode 746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 算法1递归 因为要解决的问题都是「从 0 或 1 爬到 i 」所以定义 dfs ( i ) 表示从 0 或 1 爬到 i 的最小花费。
枚举最后一步爬了几个台阶分类讨论 如果最后一步爬了 1 个台阶那么我们得先爬到 i − 1要解决的问题缩小成从 0 或 1 爬到 i − 1 的最小花费。把这个最小花费加上 cost [ i − 1 ] 就得到了 dfs ( i ) 即 dfs ( i ) dfs ( i − 1 ) cost [ i − 1 ] 。 如果最后一步爬了 2 个台阶那么我们得先爬到 i − 2要解决的问题缩小成从 0 或 1 爬到 i − 2 的最小花费。把这个最小花费加上 cost [ i − 2 ] 就得到了 dfs ( i ) 即 dfs ( i ) dfs ( i − 2 ) cost [ i − 2 ] 。 这两种情况取最小值就得到了从 0 或 1 爬到 i 的最小花费即dfs ( i ) min ( dfs ( i − 1 ) cost [ i − 1 ] , dfs ( i − 2 ) cost [ i − 2 ] ) 递归边界dfs ( 0 ) 0, dfs ( 1 ) 0。爬到 0 或 1 无需花费因为我们一开始在 0 或 1。 递归入口dfs ( n )也就是答案。
代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();functionint(int)dfs [](int i)-int{if(i 1) return 0;return min(cost[i - 1] dfs(i - 1),cost[i - 2] dfs(i - 2));};return dfs(n);}
}; 算法2递归 记录返回值 记忆化搜索 注意到「先爬 1 个台阶再爬 2 个台阶」和「先爬 2 个台阶再爬 1 个台阶」都相当于爬 3 个台阶都会从 dfs ( i ) 递归到 dfs ( i − 3 ) 。 一叶知秋整个递归中有大量重复递归调用递归入参相同。由于递归函数没有副作用同样的入参无论计算多少次算出来的结果都是一样的因此可以用记忆化搜索来优化 如果一个状态递归入参是第一次遇到那么可以在返回前把状态及其结果记到一个 memo 数组中。 如果一个状态不是第一次遇到memo 中保存的结果不等于 memo 的初始值那么可以直接返回 memo 中保存的结果。 注意memo 数组的初始值一定不能等于要记忆化的值例如初始值设置为 0并且要记忆化的 dfs ( i ) 也等于 0那就没法判断 0 到底表示第一次遇到这个状态还是表示之前遇到过了从而导致记忆化失效。一般把初始值设置为 −1。
代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint memo(n 1,-1);functionint(int)dfs [](int i)-int{if(i 1) return 0;int res memo[i];if(res ! -1) return memo[i];return res min(cost[i - 1] dfs(i - 1),cost[i - 2] dfs(i - 2));};return dfs(n);}
}; 算法31:1 翻译成递推
我们可以去掉递归中的「递」只保留「归」的部分即自底向上计算。
具体来说dp [ i ] 的定义和 dfs ( i ) 的定义是一样的都表示从 0 或 1 爬到 i 的最小花费。
相应的递推式状态转移方程也和 dfs 一样dp [ i ] min ( dp [ i − 1 ] cost [ i − 1 ] , dp [ i − 2 ] cost [ i − 2 ] ) 相当于之前是用递归去计算每个状态现在是枚举并计算每个状态。
初始值 dp [ 0 ] 0, dp [ 1 ] 0 翻译自递归边界 dfs ( 0 ) 0 , dfs ( 1 ) 0 。
答案为 dp [ n ] 翻译自递归入口 dfs ( n ) 。
代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n 1);for(int i 2;i n;i){dp[i] min(dp[i - 1] cost[i - 1],dp[i - 2] cost[i - 2]);}return dp[n];}
}; 算法4空间优化 观察状态转移方程发现一旦算出 dp [ i ] 那么 dp [ i − 2 ] 及其左边的状态就永远不会用到了。 这意味着每次循环只需要知道「上一个状态」和「上上一个状态」的 f 值是多少分别记作dp1 和 dp0 。它俩的初始值均为 0对应着 dp [ 1 ] 和 dp [ 0 ] 。 每次循环计算出新的状态 newdp min ( dp1 cost [ i − 1 ] , dp0 cost [ i − 2 ] ) 那么对于下一轮循环来说「上上一个状态」就是 dp1 更新 dp0 dp1 。「上一个状态」就是 newdp 更新 dp1 newdp 。 最后答案为 dp1 因为最后一轮循环算出的 newdp 赋给了 dp1 。代码实现时可以把 i 改成从 1 遍历到 n−1这样 newdp min ( dp1 cost [ i ] , dp0 cost [ i − 1 ] ) 可以简化一点代码。
代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();int dp0 0,dp1 0;for(int i 2;i n;i){int newdp min(dp1 cost[i - 1],dp0 cost[i - 2]);dp0 dp1;dp1 newdp;}return dp1;}
};
