C++ Solution DP with O(nk) Time and O(k) Space


  • 0
    Y
    class Solution {
    public:
        int numWays(int n, int k) {
            int ans = 0;
            if(!n || !k)
                return ans;
            vector<vector<int>> dp(2, vector<int>(k)), tmp(2, vector<int>(k));
            int sum = k;
            for(int i = 0; i < k; ++ i)
                dp[0][i] = 1;
            
            for(int i = 1; i < n; ++ i){
                for(int j = 0; j < k; ++ j){
                    tmp[0][j] = (sum - dp[0][j] - dp[1][j]);
                    tmp[1][j] = dp[0][j];
                }
                sum = 0;
                for(int j = 0; j < k; ++ j){
                    dp[0][j] = tmp[0][j];
                    dp[1][j] = tmp[1][j];
                    sum += tmp[0][j] + tmp[1][j];
                }
            }
            
            for(int i = 0; i < k; ++ i)
                ans += (dp[0][i] + dp[1][i]);
            return ans;
        }
    };

Log in to reply
 

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