Title: Three-step problem. A child is walking up a staircase. The staircase has n steps, and the child can walk up one, two or three at a time. Implement a method that counts the number of ways a child can walk up stairs. The result may be large and you need to set the result module to 1000000007. Example 1: Input: n = 3 Output: 4 Description: There are four possible paths. Example 2: Input: n = 5 Output: 13 Warning: The n range is between [1, 1000000]. Thinking: Dynamic planning: N order can be moved back, if yes, the sum of all cases of n-1 order + if yes, the sum of all cases of n-2 order + if yes, the sum of all cases of n-3 orderCopy the code

1. The code is waystostep-java:

package com.yuhl.right.leetcode;

/ * * *@author yuhl
 * @Date2020/10/25 sacrifice *@Classname WaysToStep
 * @DescriptionThree-step problem * three-step problem. A child is walking up a staircase. The staircase has n steps, and the child can walk up one, two or three at a time. Implement a method that counts the number of ways a child can walk up stairs. The result may be large and you need to set the result module to 1000000007. * * Example 1: * Input: n = 3 * Output: 4 * Description: There are four ways to go * * Example 2: * Input: n = 5 * Output: 13 * Hint: * * n The range is between [1, 1000000] */
public class WaysToStep {
    public static void main(String[] args) {
        int res = waysToStep(5);
        System.out.println(res);
    }

    / * * * *@paramN n steps *@returnGames * /
    public static int waysToStep(int n) {
        // Dynamic programming: n order can be a step back, if yes, the sum of all cases of order N-1 + if yes, the sum of all cases of order n-2 + if yes, the sum of all cases of order N-3
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        long dp1 = 1;
        long dp2 = 2;
        long dp3 = 4;
        long A = 1000000007;

        for(int i=4; i<=n; i++){
            long tmp = dp1;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = (tmp + dp1 + dp2)%A;

        }
        return (int)dp3; }}Copy the code

2. Execution Results:

"C: \ Program Files \ Java \ jdk1.8.0 _201 \ bin \ Java exe" 
13
Copy the code