15,744,149 members
See more:
Painting Fence Algorithm - GeeksforGeeks[^]

Hi everyone
In have put the link to the problem I am working on. I am trying to utilize dynamic programming to solve this problem.
I am aware that the solution is available on the website, however I would like to solve this problem without the entire solution given to me. Hence, I would really appreciate it if any of you can help me with how the tabulation table dimensions would look like (as I suspect that I have them incorrect right now) and how I can figure out the recursive formula.

What I have tried:

So far I tried solving the problem using 2D bottom up tabulation strategy, in which one dimension of the table was colors and the other dimension was fence posts.
e.g.
n = 3, k = 3
```  1 2 3
1 0 0 0
2 0 3 0
3 0 0 0
```

e.g. T[2][2] = 3 denotes that first 2 adjacent fence posts can be colored according to the problem description using 2 colors in 3 different ways
This approach unfortunately doesn't work, as I could not manage the "at most 2 adjacent fences with same color" part using a method such that I use the same method in every iteration while traversing the table.
Posted
Updated 29-Dec-22 12:34pm
v3

## Solution 1

This video should help you: Fun with Algorithms - Tess Ferrandez-Norlander - NDC Oslo 2022 - YouTube[^]. The video covers this topic very well and all code samples are in python. 😉