Leetcode DP three step problem

Log in and copy

       

        package dp.waysToStep;
        

        
/**
        
 *  Interview questions  08.01.  Three step problem 
        
 *  Three step problem . There is a child going up the stairs , The stairs have n Steps , Children can go to 1 rank 、2 Step or 3 rank . Implement a way , Calculate how many ways a child can go up stairs . The results could be big , You need to model the results 1000000007.
        
 * <p>
        
 *  Example 1:
        
 * <p>
        
 *  Input ：n = 3
        
 *  Output ：4
        
 *  explain :  There are four ways to walk 
        
 *  Example 2:
        
 * <p>
        
 *  Input ：n = 5
        
 *  Output ：13
        
 *  Tips :
        
 * <p>
        
 * n The scope is [1, 1000000] Between 
        
 */
        
public class waysToStep {
        
    public static int waysToStep(int n) {
        
        int size = n<3?3:n;
        
        int[] dp = new int[size];
        
        dp[0] = 1;
        
        dp[1] = 2;
        
        dp[2] = 4;
        
        for (int i = 3; i < n; i++) {
        
            //dp[i-3] The mold has been taken in the last step , The remaining two to prevent overflow also need to take the mold 
        
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3];
        
            dp[i] %= 1000000007;
        
        }
        
        return dp[n-1];
        
    }
        

        
    public static void main(String[] args) {
        
        System.out.println(waysToStep(1));
        
    }
        
}
       
       

        
1.
        
2.
        
3.
        
4.
        
5.
        
6.
        
7.
        
8.
        
9.
        
10.
        
11.
        
12.
        
13.
        
14.
        
15.
        
16.
        
17.
        
18.
        
19.
        
20.
        
21.
        
22.
        
23.
        
24.
        
25.
        
26.
        
27.
        
28.
        
29.
        
30.
        
31.
        
32.
        
33.
        
34.
        
35.
        
36.
        
37.
        
38.
       

Can't , I can learn ; backward , I can catch up ; Fall down , I can stand up ！