Leetcode Problem 276. Paint Fence

276. Paint Fence

Leetcode Solutions

Approach: Bottom-Up, Constant Space

  1. Initialize two variables, twoPostsBack and onePostBack, to represent the number of ways to paint the fence with one and two posts, respectively.
  2. Set twoPostsBack = k and onePostBack = k * k to represent the base cases.
  3. Iterate from the third post to the n-th post.
  4. For each iteration, calculate the number of ways to paint the current post using the recurrence relation: curr = (k - 1) * (onePostBack + twoPostsBack).
  5. Update twoPostsBack to the value of onePostBack, and onePostBack to the value of curr.
  6. After the loop, return the value of onePostBack as the final answer.
UML Thumbnail

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

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...