大型游戏门户网站织梦模板,青岛手机网站设计公司,网站后台shopadmin输在哪里,网站开发工作室 建设 方案leetcode 746 使用最小花费爬楼梯 虽然是简单题但还是要说一下,感觉做题的思路还是不够清晰,好的是知道状态是最低花费,知道围绕所求的目标进行展开,倒推出递推公式
一开始写的递推公式是dp[i]dp[i-1]min(cost[i-2],cost[i-1]),写出了一个类似贪心算法的东西,归根结底还是对dp…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的长度(最后一个元素的下一位)
