【剑指 Offer 10- II. 青蛙跳台阶问题】

￡神魔★判官ぃ 2023-09-26 16:29 2阅读 0赞

package com.example.demomain.demoleetcode.easy;
    
    import org.junit.Test;
    
    /**
     * @author: lfsun
     * @time: 18:24
     * @date: 2022/11/13
     */
    public class NumWays {
        
    
        /**
         * 动态规划
         *
         * @param n
         * @return
         */
        public int numWaysByDp(int n) {
        
            if (n == 0 || n == 1) {
        
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
        
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
            return dp[n];
        }
    
        /**
         * 递归超时
         *
         * @param n
         * @return
         */
        public int numWaysByRecursive(int n) {
        
            if (n == 0 || n == 1) {
        
                return 1;
            }
            return (numWaysByRecursive(n - 1) + numWaysByRecursive(n - 2)) % 1000000007;
        }
    
        /**
         * 针对普通的动态规划优化了空间复杂度
         *
         * @param n
         * @return
         */
        public int numWaysByDpPlus(int n) {
        
            if (n == 0 || n == 1) {
        
                return 1;
            }
            int pre = 1, cur = 2;
            for (int i = 3; i <= n; i++) {
        
                int tmp = (pre + cur) % 1000_000_007;
                pre = cur;
                cur = tmp;
            }
            return cur;
        }
    
        @Test
        public void test() {
        
            int n = 0;
            System.out.println(numWaysByDp(n));
    
        }
    }