题目分析

爬楼梯问题大家都已经很熟悉了，这个问题比爬楼梯问题稍微复杂一些，不过思路和方法都是类似的，小伙伴们还记得如何求解吗？

记忆化+DFS

经典的爬楼梯问题和斐波那契数列问题是相同的，可以通过记忆化+DFS或者DP来求解。

我们要求从0号或者1号位置出发到达n的最小花费。我们可以从后向前计算，令dfs(k)代表从k出发到达n的最小花费，先算从n - 1出发到达n的最小花费，从n - 2出发的最小花费……

从k出发可以到k + 1索引，也可以到达k + 2索引，因此我们要求从k出发的最小花费，就要求min(dfs(k + 1), dfs(k + 2)) + cost[k]。为了节省冗余计算，我们使用一个哈希表记住从k出发的最小花费，这样递归的时候可以进行剪枝。

最后比较dfs(0)和dfs(1)的最小值即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>

using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        unordered_map<int, int> mem;
        int length = cost.size();
        return min(dfs(cost, 0, mem, length), dfs(cost, 1, mem, length));
    }

    int dfs(vector<int>& cost, int idx, unordered_map<int, int>& mem, int& length) {
        if (idx >= length) { return 0; }
        if (!mem.count(idx)) { mem[idx] = min(dfs(cost, idx + 1, mem, length), dfs(cost, idx + 2, mem, length)) + cost[idx]; }
        return mem[idx];
    }
};

DP

我认为DP解法是解决这类问题的最优解法，也是需要小伙伴掌握的一种解法。

其实DFS+记忆化本质上就是一种DP思想，只不过用递归的方式进行实现罢了。

DP介绍的是从前向后的计算方法，令dp[k]是到达k的最小花费，先算到达2的最小花费，到达3的最小花费……

从k - 2出发可以到k索引，从k - 1出发也可以到达k索引，因此我们要求到达k的最小花费，就要求min(dp[k - 1], dp[k - 2]) + cost[k]。因为我们每次只用到前两次的数据，因此我们还可以进一步减小空间复杂度。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

刷题总结

爬楼梯问题太经典了，小伙伴们一定要学会DP求解的思路。如果还能提出DFS+记忆化的方案，也能给你在面试中的表现大大加分，可能不需要写DFS+记忆化的过程，只需要实现DP，然后口述记忆化的流程即可。