leetcode-面试题 08.01. 三步问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int waysToStep(int n) {

        if (n < 3) {
            return n;
        }
        if (n == 3) {
            return 4;
        }

        //定义三个状态
        long[] dp = new long[n + 1];

        //初始化dp
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

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