简单动态规划-爬楼梯的最小代价

这里直接给个leetcode的链接吧，本人太懒了不想写题干。

题目

所谓的到楼梯顶就是要越过这个数组。比如数组长度为n，那么就要抵达n这个位置。一开始我觉得很难，不知道怎么做，因为它说可以从0开始，也可以从1开始，那我怎么知道从0开始还是从1开始？而且，你到某个地方后，还得根据那个值判断是跳两格还是只跳一格，这就很狗了。而且而且，貌似这道题跟以前的题不一样啊，以前的动态规划题都不会越过数组的，你这要我怎么从数组最后一个元素开始分析？

后来一看题解，哈哈只能说我题目做得太少了。

先来说说动态规划的解法：

根本不需要考虑那么多乱七八糟的事情，dp数组开到cost数组长度+1就行了。然后，对于某一个位置i,我们随便分析一下就能知道，能跳到这个位置，那无非只有两种情况，一是从i-1这个位置跳过来，二是从i-2这个位置跳过来。然后，因为题目要求的最小代价之和，那我肯定要记录之前已经花费的所有代价，因此，动态规划方程就是：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).

 1 public int calMinCost(int[] cost) {
 2         int n = cost.length;
 3         int[] dp = new int[n+1];
 4         dp[0] = 0;
 5         dp[1] = 0;
 6         for (int i = 2; i <= n; ++i) {
 7             dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
 8         }
 9         return dp[n];
10 }

但是这样做的空间复杂度为O(n),我们可以优化一下：

可以看到其实最终的代价之和只与cost数组有关，那我们完全可以用两个变量来模拟dp数组，只需要有限的额外空间。

 1 public int calMinCost(int[] cost) {
 2         int n = cost.length;
 3         int pre = 0;
 4         int cur = 0;
 5         for (int i = 2; i <= n; ++i) {
 6             int next = Math.min(cur + cost[i-1], pre + cost[i-2]);
 7             pre = cur;
 8             cur = next;
 9         }
10         return cur;
11 }

这样就行了。