# A derivation that might be easier to understand

• It might be easier to think of it this way:

ns[i] means the total number of color scheme of post 1 to i if post i does not have the same color as post i-1.

s[i] means the total number of color scheme if post i has the same color as post i-1;

``````ns[i] = ( ns[i-1] + s[i-1] ) * (k-1)
``````

this is because if we restrict that post i does not have the same color as post i-1, then we can choose whatever color for post i, except for the color painted on post i-1 （definition of ns[]), so (k-1) choice for each previous color scheme.

``````s[i] = ns[i-1]
``````

this is because if we restrict that post i has the same color as post i-1, then from the previous color scheme, we can only choose those of ns[i-1] (where post i-1 does not have the same color as post i-2), otherwise there will be three continuous posts with the same color. For each such scheme we have only one color choice for post i since it has to be the color of post i-1.

Note we obtain the same equations as in:

https://leetcode.com/discuss/56146/dynamic-programming-c-o-n-time-o-1-space-0ms

But perhaps it is easier to think of it in this way.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.