Painting the Fence

// Approach: DP. Track same (last two posts same color) and diff (different color).
// same[i] = diff[i-1], diff[i] = total[i-1] * (k-1). Total = same + diff.
// Time: O(n) Space: O(1)
class Solution {

    int countWays(int n, int k) {
        // There are k ways to color first post
        int total = k;

        // There are 0 ways for single post to
        // violate (same color_ and k ways to
        // not violate (different color)
        int same = 0, diff = k;

        // Fill for 2 posts onwards
        for (int i = 2; i <= n; i++) {
            // Current same is same as previous diff
            same = diff;

            // We always have k-1 choices for next post
            diff = ((int) total * (k - 1));

            // Total choices till i.
            total = (same + diff);
        }
        
        return total;
    }
}