当前位置：首页 > news >正文

leetcode：面试题 08.01. 三步问题

news 2025/6/23 8:56:02

题目链接

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

解法三：递归法

//方法三：但是测试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);}