LeetCode 276: Paint Fence

Explanation:

The problem asks us to paint a fence with n posts, and there are k colors to choose from. We need to find the total number of ways to paint the fence such that no more than two adjacent posts have the same color.

To solve this problem, we can use dynamic programming. We can maintain two variables, same and different, to represent the number of ways to paint the current post the same color as the previous post and a different color from the previous post, respectively.

For each post, we can calculate the new values of same and different based on the previous states. The new value of same is equal to the previous value of different because we can only paint the current post the same color as the previous post if the previous post is a different color. The new value of different is the sum of the previous values of same and different multiplied by k-1 because we can paint the current post a different color in k-1 ways.

We iterate through all posts and update the values of same and different accordingly. Finally, the total number of ways to paint the fence is the sum of the final values of same and different.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of posts.

Space Complexity:

The space complexity of this approach is O(1) since we are using only two variables to store the values of same and different.

:

class Solution {
    public int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;

        int same = 0, different = k;
        for (int i = 2; i <= n; i++) {
            int newSame = different;
            int newDifferent = (same + different) * (k - 1);
            same = newSame;
            different = newDifferent;
        }
        return same + different;
    }
}