Paint Fence

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

• Every post must be painted exactly one color.
• There cannot be three or more consecutive posts with the same color.

Example 1:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Input: n = 1, k = 1
Output: 1

Input: n = 7, k = 2
Output: 42

• 1 <= n <= 50
• 1 <= k <= 10⁵
• The test cases are generated such that the answer is in the range [0, 2³¹ - 1] for the given n and k.

Approach 1: Top-Down Dynamic Programming (Recursion + Memoization)

Top-down dynamic programming starts from the top and works its way down to the base cases.
Typically, this is implemented with recursion and then made efficient using memoization.
Memoization refers to storing the results of expensive function calls to avoid duplicate computations - we'll soon see why this is important for this problem.
We can implement the function totalWays(i) as follows - first, check for the base cases we defined above: totalWays(1) = k, totalWays(2) = k * k.
If i >= 3, use our recurrence relation: totalWays(i) = (k - 1) * (totalWays(i - 1) + totalWays(i - 2)).
However, we will run into a major problem - repeated computation.
If we call totalWays(5), that function call will also call totalWays(4) and totalWays(3).
The totalWays(4) call will call totalWays(3) again.
As illustrated below, we are calculating totalWays(3) twice.

This may not seem like a big deal with i = 5, but imagine if we called totalWays(6).
This entire tree would be one child, and we would have to call totalWays(4) twice. As n increases, the size of the tree grows exponentially - imagine how expensive a call such as totalWays(50) would be.
This can be solved with memoization. When we compute the value of a given totalWays(i), let's store that value in memory.
Next time we need to call totalWays(i), we can refer to the value stored in memory instead of having to call the function again and going through the repeated computations.

Algorithm

• Define a hash map memo, where memo[i] represents the number of ways you can paint i fence posts.
• Define a function totalWays where totalWays(i) will determine the number of ways you can paint i fence posts.
• In the function totalWays, first check for the base cases. Return k if i == 1, and return k * k if i == 2. Next, check if the argument i has already been calculated and stored in memo. If so, return memo[i]. Otherwise, use the recurrence relation to calculate memo[i], and then return memo[i].
• Simply call and return totalWays(n).

Complexity Analysis

Time complexity: O(n) totalWays gets called with each index from n to 3.
Because of our memoization, each call will only take O(1) time.
Space complexity: O(n) The extra space used by this algorithm is the recursion call stack.
For example, totalWays(50) will call totalWays(49),
which calls totalWays(48) etc.,
all the way down until the base cases at totalWays(1)
and totalWays(2).
In addition, our hash map memo will be of size n at the end,
since we populate it with every index from n to 3.

class Solution {
      private HashMap memo = new HashMap();
      private int totalWays(int i, int k) {
         if (i == 1) return k;
         if (i == 2) return k * k;

         // Check if we have already calculated totalWays(i)
         if (memo.containsKey(i)) {
            return memo.get(i);
         }

         // Use the recurrence relation to calculate totalWays(i)
         memo.put(i, (k - 1) * (totalWays(i - 1, k) + totalWays(i - 2, k)));
         return memo.get(i);
      }

      public int numWays(int n, int k) {
         return totalWays(n, k);
      }
}    
              

Time Complexity: O(n) and Space Complexity: O(n)