A derivation that might be easier to understand


  • 3
    F

    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.


Log in to reply
 

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