C++ O(n) dp solution with thorough explanation.


  • 0
    W
    class Solution {
    public:
        int numWays(int n, int k) {
            /*
                dp[i][0] = nr of ways to paint fences 0 to i, when fence i and fence (i-1) have not the same colour.
                dp[i][1] = nr of ways to paint fences 0 to i, when fence i and fence (i-1) have the same colour.
            */
            if(n == 0)
                return 0;
            if(n <= 2)
                return int(pow(k,n));   // n = 1 => ways = k, n = 2 => ways = k * k
            vector<vector<int> >dp(n, vector<int>(2,0));
            // base cases
            dp[0][0] = dp[0][1] = k; 
            dp[1][0] = k*(k-1);
            dp[1][1] = k; // when fence 0 and fence 1 have the same colour, then possible colours are cc, where 1<=c<=k.
            for(int i=2; i<n; ++i){
                // if fence i and i-1 should not have same colour, then fence i has only k-1 possible colours.
                dp[i][0] = (k-1) * (dp[i-1][0] + dp[i-1][1]);
                // if fence i and i-1 have same colour, then fence i-2 should not have the same colour, and this is captured by
                // dp[i-1][0].
                dp[i][1] = dp[i-1][0];
            }
            // final result is by painting fences 0 to n-1, with fence n and n-1 having the same colour or not.
            return dp[n-1][0] + dp[n-1][1];
            
        }
    };
    

Log in to reply
 

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