0070 Climb Stairs

• Simple
• C++, 递归, 动态规划DP,

问题概述

解题思路

// 方法：递归方法
// 结果：leetcode不通过：时间超时
// 分析：当n很大的时候，递归好多次，每次递归都会有重复运算
class Solution
{
public:
    int climbStairs(int n)
    {
        if (n == 1) return 1;
        if (n == 2) return 2;

        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

// 递归法
// 存储已经计算过的
// accepted

class Solution
{
public:
    int climbStairs(int n)
    {
        int* memory = new int[n + 1];
        int result = calculate(n, memory);
        delete[] memory;
        return result;
    }

    int calculate(int n, int* memory)
    {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (memory[n] > 0) return memory[n];

        memory[n] = calculate(n - 1, memory) + calculate(n - 2, memory);
        return memory[n];
    }
};

// 动态规划问题，DP
// 动态规划本质上就是：递归 + 记忆化
class Solution
{
public:
    int climbStairs(int n)
    {
        std::vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < n + 1; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

// DP问题
// version3中把n的每个值都存储了，但实际上并不需要，只需要知道此时的n的前两个数值就好

class Solution
{
public:
    int climbStairs(int n)
    {
        int dp_i_1 = 1;
        int dp_i_2 = 1;

        for (int i = 2; i < n + 1; ++i)
        {
            int dp = dp_i_1 + dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp;
        }
        return dp_i_1;
    }
};