Click here to Skip to main content
15,868,164 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

1 solution

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. 😉
 
Share this answer
 

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



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