Paint Fence

XXX. Paint Fence

Dynamic Programming

Problem Statement:

You are tasked with painting a fence with n posts using k colors. Each post can be painted in one of the k colors. You must ensure that no more than two adjacent fence posts have the same color.

Return the total number of ways to paint the fence while satisfying this condition.

Algorithm:

This problem can be solved using dynamic programming. The key is to calculate the number of valid ways to paint up to the current post based on the ways to paint the previous posts.

1. Base Cases:
   • If there are no posts (n == 0), return 0 because there is nothing to paint.
   • If there is one post (n == 1), any of the k colors can be used, so the answer is k.
   • If there are two posts (n == 2), the first post can be painted in k ways. The second post can either have the same color (k ways) or a different color (k * (k - 1) ways). The total is k * k.
2. Key Insight:

   For any post after the second, the number of ways to paint it depends on:

   • If the current post has the same color as the previous post, the two previous posts must have different colors. This is why we multiply by k - 1, which excludes the color of the last post.
   • If the current post has a different color than the previous post, it can be painted in k - 1 ways as well, since we exclude the color of the previous post.
3. Dynamic Programming Transition:

   Define:

   • pre2: The number of ways to paint up to the previous-to-last post.
   • pre1: The number of ways to paint up to the last post.
   • curr: The number of ways to paint the current post.

   Use the recurrence relation:

   • curr = (pre2 + pre1) * (k - 1)

   Here, (pre2 + pre1) represents all valid ways to paint up to the previous two posts, and (k - 1) ensures that the current post avoids the color of the last post.

4. Iterate from the third post to the nth post, updating pre2, pre1, and curr at each step.
5. Return curr as the total number of ways to paint the fence.

Complexity:

Time Complexity: O(n), where n is the number of posts. We iterate through all the posts.
Space Complexity: O(1), since only a few variables are used to store intermediate results.

Java Implementation:

class Solution {
    public int numWays(int n, int k) {
        // Edge cases: no posts or one post
        if (n == 0) return 0; // No posts to paint
        if (n == 1) return k; // Only one post, any color can be used
        if (n == 2) return k * k; // Two posts, same or different colors

        // Initialize variables for dynamic programming
        int pre2 = k;           // Ways to paint up to the previous-to-last post
        int pre1 = k * k;       // Ways to paint up to the last post
        int curr = 0;           // Ways to paint the current post

        // Iterate from the third post to the nth post
        for (int i = 3; i <= n; i++) {
            // Calculate the number of ways to paint the current post
            curr = (pre2 + pre1) * (k - 1); // (k - 1) ensures no two adjacent posts have the same color
            pre2 = pre1;        // Update pre2 for the next iteration
            pre1 = curr;        // Update pre1 for the next iteration
        }

        return curr; // Return the total number of ways to paint n posts
    }
}