leetcode 每日一题复盘(11.20~11.26)

leetcode 746 使用最小花费爬楼梯

虽然是简单题但还是要说一下,感觉做题的思路还是不够清晰,好的是知道状态是最低花费,知道围绕所求的目标进行展开,倒推出递推公式

一开始写的递推公式是dp[i]=dp[i-1]+min(cost[i-2],cost[i-1]),写出了一个类似贪心算法的东西,归根结底还是对dp状态的认识不过,不清楚i代表什么,dp代表什么

实际上dp代表的是到达某一层的最低花费,而i则是层数,上面就是对i的代表不明确导致的,正确的推导公式应该是dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]),选择从i-1层和i-2层到达i层两者的最小值

其他的没什么好讲的,也就是题目表达的不是很好,有点难理解,需要跨越数组的最后一个元素(下标为n)才是到达楼顶而不是到达最后一个元素(下标n-1) 

因此我们最后取dp的下标是n,也就是数组cost的长度(最后一个元素的下一位)