10.青蛙跳台阶问题

参考链接

剑指offer_在线编程_ - 牛客网

剑指 Offer 10- II. 青蛙跳台阶问题-跟着帅地玩转校招，刷爆各类算法题 - 帅地玩Offer

LCR 127. 跳跃训练 - 力扣（LeetCode）

个人尝试

class Solution {
    public int trainWays(int num) {
        int[] dp = new int[num + 1];
        if (num == 0 || num == 1) return 1;
        dp[0] = 1; dp[1] = 1;
        
        for (int i = 2; i <= num; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }

        return dp[num];
    }
}

参照题解，将原本的空间复杂度 O(n) 优化成 O(1)，多了两步赋值过程

class Solution {
    public int trainWays(int num) {
        if (num == 0 || num == 1) return 1;

        int[] dp = new int[3];
        dp[0] = 1; dp[1] = 1;
        
        for (int i = 2; i <= num; i++) {
            dp[2] = (dp[0] + dp[1]) % 1000000007;
            dp[0] = dp[1];
            dp[1] = dp[2];
        }

        return dp[2];
    }
}

优秀题解

class Solution {
    public int trainWays(int num) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < num; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solutions/101617/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。