【LeetCode每日一题】——面试题08.01.三步问题-创新互联

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【解题思路】
七【题目提示】
八【时间频度】
九【代码实现】
十【提交结果】

创新互联公司是一家专注于成都网站设计、成都网站制作与策划设计,涪陵网站建设哪家好?创新互联公司做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:涪陵等地区。涪陵做网站价格咨询:18982081108一【题目类别】

动态规划

二【题目难度】

简单

三【题目编号】

面试题 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

【LeetCode每日一题】——面试题08.01.三步问题-创新互联

其他资讯