leetcode【746-使用最小花费爬楼梯】思考、优化、改进

灰太狼 2022-10-28 12:27 181阅读 0赞

声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

# 1.题目&示例 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]

# 2.分析 #

这个题目是一个标准的DP问题，DP问题还是先考虑这几个基本问题  
**dp数组每一项的含义、状态转移方程、初始值**  
dp数组中每一项dp\[i\]的含义应为：到达该第i层所需要的最少花费  
状态转移方程为：dp\[i\] = min\{dp\[i-1\]+cost\[i-1\]，dp\[i-2\]+cost\[i-2\]\}  
初始值：dp\[0\] = dp\[1\] = 0;  
dp\[n\]即为所求

# 3.代码 #

class Solution { 
    public:
        int minCostClimbingStairs(vector<int>& cost) { 
    	vector<int> dp(cost.size()+1,0);
        for(int i=2;i<cost.size()+1;i++)
        { 
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
        }
    };

![在这里插入图片描述][2021020614463664.png]  
还可以进一步简化，观察状态转移方程：  
dp\[i\] = min\{dp\[i-1\]+cost\[i-1\]，dp\[i-2\]+cost\[i-2\]\}  
无需维护整个数组，仅仅需要暂存dp\[i-1\],dp\[i-2\]两个临时变量即可,代码如下：

class Solution { 
    public:
        int minCostClimbingStairs(vector<int>& cost) { 
    	int tmp1 =0, tmp2 = 0,res = 0;
        for(int i=2;i<cost.size()+1;i++)
        { 
            res = min(tmp1+cost[i-2],tmp2+cost[i-1]);
            tmp1 = tmp2;
            tmp2 = res;
        }
        return res;
        }
    };

![在这里插入图片描述][20210206145207487.png]  
更快了一步，尤其是处理长数据的情况下尤为明显。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjI0MDMw_size_16_color_FFFFFF_t_70]: /images/20221024/6294b7ac6df84c35b13915d47b4bacc5.png
[2021020614463664.png]: /images/20221024/6cd9ee539310449eb1bfa1cf17401ff9.png
[20210206145207487.png]: /images/20221024/b0beab5769a64b58ae3a2dd29c656be3.png