Given a wall of L*W size. The wall is made up of bricks of sizes 1*1. We need to color the wall with K(given) colors such that no two adjacent bricks (bricks sharing a side) get the same coloring. How many ways to do achieve that?
constraint: K, L and W are in the range of 100000
Obviously, it is a DP problem. But giving a solution would kill your opportunity to learn.
Rather, there is a similar problem that appeared in Topcoder. Here is the Editorial for the same -
https://apps.topcoder.com/wiki/display/tc/SRM+532
Go through it and learn the concept of Profiling. That would help you in solving your problem.
Where is the problem link? Is it from an ongoing contest?
No, it is not from any contest. I remember this QS from some OJ, idk the name of the OJ.