10 lines concise and easy understanding DP solution dp[n] = dp[n - 1] * k - dp[n - 3] * (k - 1)


  • 0
    A

    dp[n] = dp[n - 1] * k - dp[n - 3] * (k - 1)

    class Solution {
    public:
        int numWays(int n, int k) {
            vector<int> ans{k, k * k, k * k * k - k};
            if(n == 0) return 0;
            if(n <= 3) return ans[n - 1];
            for(int i = 3; i < n; i++) {
                int tmp = ans[2];
                ans[2] = ans[2] * k - ans[0] * (k - 1);
                ans[0] = ans[1];
                ans[1] = tmp;
            }
            return ans[2];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.