15,663,399 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. 😉

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 steveb 75 OriginalGriff 70 CPallini 45 Graeme_Grant 40 Rick York 10
 OriginalGriff 2,203 Graeme_Grant 1,041 Richard Deeming 728 Richard MacCutchan 648 Dave Kreskowiak 473

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900