LeetCode 面試題 08.01. 三步問題 (動态規劃)

面試題 08.01. 三步問題

解法1（動态規劃）

• 分析出遞推式：f(n) = f(n - 1) + f(n - 2) + f(n - 3)

class Solution {
    public int waysToStep(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        
        long[] dp = new long[n + 1];
        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];
    }
}