276. Paint Fence

/*
T: O(n)
S: O(n)


一般來說 k種顏色的塗法
如果 two posts 是相同: 那就 k
如果 two posts 是不相同: 那就 k＊(k-1)

看最後三個 posts
  i-1    i
a  b     c

dp[i] = 
post b, c 塗一樣時 (y==z) => post a, b 一定要不一樣色

post b, c 塗不一樣時 (y != z) => post a, b 可以 一樣色 or 不一樣色

status:
same[i]: # of methods that satisfied nums[k-1] == nums[k]
diff[i]: # of methods that satisfied nums[k-1] != nums[k]

so same[i] = diff[i-1]   
   // 因為 最後 b c 固定相同(same[i]), 所以 a b 一定不一樣（所以直接用狀態 diff[i-1] 表示）
   // 然後不用在選色了 因為 bc 一樣, 所以在 diff[i-1] 時就會決定 b 的顏色, 所以也就會決定 c 的顏色
   
   diff[i] = same[i-1]*(k-1) + diff[i-1]*(k-1) 
   // 最後 bc 不一樣時, ab 可以一樣*(k-1)種顏色去決定 diff[i]   
   // ab可以不一樣*(k-1)種顏色去決定 diff[i]   

dp[i][0,1]: when dp[i][same] or dp[i][different], 
i is posts（two posts）, the number of ways you can paint the fence.
i is posts（two posts）
0: two posts are the same
1: two posts are different


dp[i][0] = dp[i-1][1]

dp[i][1] = dp[i-1][0]*(k-1) + dp[i-1][1]*(k-1)


so 

        for (int i = 3; i <= n; i++) { // why start from 3? because at least 2 posts can decide same or diff
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][0]*(k-1) + dp[i-1][1]*(k-1);
        }

dp[3][0] = dp[2][1]; // 因為 2, 3 same,  so 1,2 不能是 same, is diff

dp[3][1] = = dp[2][0]*(k-1) + dp[2][1]*(k-1)       // 因為 2, 3 diff, so 1,2 可以是 same, 也可以是 diff
*/

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) {
            return k; // when 1 post, have k ways to paint
        }
        int[][] dp = new int[n+1][2];
    
        dp[2][0] = k;
        dp[2][1] = k*(k-1);
        
        for (int i = 3; i <= n; i++) { // why start from 3? because at least 2 posts can decide same or diff
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][0]*(k-1) + dp[i-1][1]*(k-1);
        }
        
        return dp[n][0] + dp[n][1];
    }
}

or

class Solution {
    public int numWays(int n, int k) {

        int[][] dp = new int[n][2];
        
        dp[0][0] = 0; // 0: 跟上個 same color
        dp[0][1] = k; // 1: 跟上個 diff color
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][1]; // i 跟前個相同, 所以 i-1 要不同
            dp[i][1] = (dp[i-1][0] + dp[i-1][1])*(k-1); // i 跟前個不同, 所以 i-1 （可以同 可以不同）＊(k-1
        }
        return dp[n-1][0] + dp[n-1][1];
    }
}

/*
dp[i][0,1]
number of ways you can paint the fence.

*/

use variable

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) {
            return k; // when 1 post, have k ways to paint
        }    
        int same = k;
        int diff = k*(k-1);
        
        for (int i = 3; i <= n; i++) { // why start from 3? because at least 2 posts can decide same or diff
            int sameTmep = same;
            int diffTemp = diff;
            
            same = diffTemp;
            diff = sameTmep*(k-1) + diffTemp*(k-1);
        }
        
        return same + diff;
    }
}

DFS + memo

class Solution {
        
    public int numWays(int n, int k) {
        Integer[] memo = new Integer[n+1];
        return totalWays(n, k, memo);
    }
    
    private int totalWays(int i, int k, Integer[] memo) {
        if (i == 1) return k;
        if (i == 2) return k * k;
        
        // Check if we have already calculated totalWays(i)
        if (memo[i] != null) {
            return memo[i];
        }
        
        // totalWays(i - 1, k) => 跟前面不同
        // totalWays(i - 2, k) => 跟前面相同
        memo[i] = (k - 1) * (totalWays(i - 1, k, memo) + totalWays(i - 2, k, memo));
        return memo[i];
    }
}