FunctionRacerProblemsRace

Paint the Fence

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

A fence has n posts and you have k colors. Paint every post one color so that no three posts in a row share a color (two in a row are fine). Return the number of valid ways to paint the fence.

Example 1

n 3
k 2
returns 6

Of the 8 colorings, the two with all equal are invalid, leaving 6.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems