【LeetCode每日一题】——面试题08.01.三步问题-创新互联
文章目录
网站标题:【LeetCode每日一题】——面试题08.01.三步问题-创新互联
网站链接:http://myzitong.com/article/dhppos.html
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【解题思路】
- 七【题目提示】
- 八【时间频度】
- 九【代码实现】
- 十【提交结果】
- 动态规划
- 简单
- 面试题 08.01.三步问题
- 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
示例1:
- 输入:n = 3
- 输出:4
- 说明: 有四种走法
示例2:
- 输入:n = 5
- 输出:13
- 此题比较简单,属于动态规划的入门题目,同时也是组合数学喜欢考的题型
- 每一级台阶只有三种可能:
- 从前三级跳三阶
- 从前二级跳二阶
- 从前一级跳一阶
- 在动态规划中,默认当前位置之前都是已经计算出来了
- 所以第 i i i阶台阶可能的跳法就是第 i − 1 i-1 i−1阶+第 i − 2 i-2 i−2阶+第 i − 3 i-3 i−3阶的跳法之和,所以,动态转移方程为: d p [ i ] = ( ( d p [ i − 1 ] + d p [ i − 2 ] ) + d p [ i − 3 ] ) dp[i] = ((dp[i - 1] + dp[i - 2]) + dp[i - 3]) dp[i]=((dp[i−1]+dp[i−2])+dp[i−3])
- 另外还需要注意边界问题,当阶数小于等于3时,可以直接返回
- 还有取模的细节也要注意,因为动态转移方程前两个就可能很大了,所以需要先取一次模,整体计算完后还需要取一次模
- 最后返回结果即可
- n n n范围在 [ 1 , 1000000 ] [1, 1000000] [1,1000000]之间
- 时间复杂度: O ( n ) O(n) O(n),其中 n n n为数组大小
- 空间复杂度: O ( n ) O(n) O(n),其中 n n n为数组大小
- Java语言版
class Solution {public int waysToStep(int n) {if(n == 1){return 1;
}
if(n == 2){return 2;
}
if(n == 3){return 4;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4;i<=n;i++){dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
}
return dp[n];
}
}
- C语言版
int waysToStep(int n)
{if(n == 1)
{return 1;
}
if(n == 2)
{return 2;
}
if(n == 3)
{return 4;
}
int* dp = (int*)malloc(sizeof(int) * (n + 1));
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4;i<=n;i++)
{dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
}
return dp[n];
}
- Python版
class Solution:
def waysToStep(self, n: int) ->int:
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return 4
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,n+1):
dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007
return dp[n]
十【提交结果】Java语言版
C语言版
Python语言版
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站标题:【LeetCode每日一题】——面试题08.01.三步问题-创新互联
网站链接:http://myzitong.com/article/dhppos.html