LC: Paint Fence - spiralgo/algorithms GitHub Wiki

Paint Fence

The Essence:

At the second fence, count for having the last two fences is equal to k. The count for different is k*(k-1). At the third fence, count for having the last two fences is depended on having the previous two different. That's the only way the fences can be valid. The value for this is then k*(k-1). The count for different is sum of both previous cases times some another color (prev_same+prev_diff)*(k-1).

From this, the program can build up the solution to the i'thfence:

count[i] = diff[i] + same[i] = (diff[i-1]+same[i-1])*(k-1) + diff[i-1]

Details:

This linear recursive definition of the count is naturally solvable in a bottom-up fashion using dynamic programming. The problem-solvers need to acquaint themselves using dynamic programming for wide range of problems such as this discrete mathematics-like problem and graph traversal problems.

The code implementation as well as visualization of this algorithm can be found here: https://github.com/spiralgo/algorithms/pull/296