leetcode：面试题 08.01. 三步问题

题目链接

        面试题 08.01. 三步问题 - 力扣（LeetCode）

题目描述

解法一：

int waysToStep(int n) {
    // dp[i]--->爬到第i阶楼梯的最大方式
    // dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;
    vector<int> dp(n+1);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    // dp[4] = 7; dp[5] = dp[4] + dp[3] + dp[2] = 13;
    for(int i = 4; i <= n; i++)
    {
        dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
    }
    return dp[n];
}

解法二：

// dp[i][1]--->从上一个台阶进入此台阶，爬楼梯的最大方式
// dp[i][2]--->从上二个台阶进入此台阶，爬楼梯的最大方式
// dp[i][3]--->从上三个台阶进入此台阶，爬楼梯的最大方式
 int waysToStep(int n) {
     if(n == 1) return 1;
     if(n == 2) return 2;
     if(n == 3) return 4;
     vector<vector<int>> dp(n+1,vector<int>(4));
     dp[1][1] = 1; dp[1][2] = 0; dp[1][3] = 0;
     dp[2][1] = 1; dp[2][2] = 1; dp[2][3] = 0;
     dp[3][1] = 2; dp[3][2] = 1; dp[3][3] = 1;
     for(int i = 4; i <= n; i++)
     {
         dp[i][1] = ((dp[i-1][1] + dp[i-1][2]) % MOD + dp[i-1][3]) % MOD;
         dp[i][2] = ((dp[i-2][1] + dp[i-2][2]) % MOD + dp[i-2][3]) % MOD;
         dp[i][3] = ((dp[i-3][1] + dp[i-3][2]) % MOD + dp[i-3][3]) % MOD;
     }
     return ((dp[n][1] + dp[n][2]) % MOD + dp[n][3]) % MOD;
 }

解法分析

1. 解法1与解法2比较之下，肯定是解法1更加合适，方便
2. 两种解法都是采用动态规划思想去解决问题，也就是说采用动态规划方法去解决问题时，不止一种思考方式
3. 动态规划法去解决问题时，宏观逻辑是，利用计算机的记忆，把每种情况都记住，然后一步步迭代，这次迭代的过程，依赖上次迭代的结果，上次迭代的结果被计算机存储了。
4. 可以说动态规划是在一步步的暴力穷举，只有走了第一步，才能走好第二步。只有走了第二步，才能走好第三步
5. 动态规划在记什么：在记状态，你决定如何考虑状态，就决定你要怎么走
6. 最好怎么考虑状态：状态最少的状态，就是解决问题最好的状态

解法三：递归法

//方法三：但是测试99时已经超出时间显示
    int dfs(int n)
    {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        int n1 = dfs(n-1);
        int n2 = dfs(n-2);
        int n3 = dfs(n-3);
        return n1 + n2 + n3;
    }
    int waysToStep(int n) {
        return dfs(n);
    }

解法分析

1. 纯递归也可以解决问题，仅仅只是数据量太大时，超过时间限制而已
2. 也就是说，动态规划是解决该问题的一个方法，也可以用其它方法来解决问题
3. 也就是说这道题不是动态规划本身，动态规划算法是解决这道题的一个方法
4. 也就是说这道题，利用了计算机的存储结构，这是计算机对动态规划算法做出的贡献
5. 人脑决定了计算机存储什么，这是人脑对动态规划算法做出的贡献
6. 人脑根据如何分类状态，决定如何计算机如何存储数据
7. 也就是说动态规划算法== 人脑根据智力分类状态 + 计算机存储状态 + 计算机迭代