Dynamic programming, C++, O(n) time, O(1) space, 0ms


  • 25
    J

    Need two one-dimensional array dp1 and dp2,
    dp1[i] means the number of solutions when the color of last two fences (whose indexes are i-1,i-2) are same.
    dp2[i] means the number of solutions when the color of last two fences are different.

    So

    dp1[i]=dp2[i-1],

    dp2[i]=(k-1)(dp1[i-1]+dp2[i-1]) =(k-1)(dp2[i-2]+dp2[i-1])**

    Final result is dp1[n-1]+dp2[n-1];

    In the code, variable a,c mean the last two items of dp1, variable b,d mean the last two items of dp2, and c could be eliminated.

    class Solution {
    public:
        int numWays(int n, int k) {
            if(n<=1 || k==0)return n*k;
            int a=k,b=k*(k-1),c=0,d=0;
            for(int i=2;i<n;++i){
                d=(k-1)*(a+b);
                a=b;b=d;
            }
            return a+b;
        }
    };

  • 0
    S

    I don't understand why we need to calculate solutions when last two fences have the same color? Why dp1[n-1] + dp2[n-1] is the final result? Can anybody explain it a little bit?


  • 0
    S

    @steven10 See my answer


  • 3

    Great code and explanation! I rewrite it a little bit: s means same and stands for the last element of your dp1; d means different, d1 and d2 stands for the last two elements of your dp2.

    In each loop, dp1[i] = dp2[i - 1] turns into s = d2 and dp2[i] = (k - 1) * (dp2[i - 2] + dp2[i - 1]) becomes d2 = (k - 1) * (d1 + d2). Moreover, d1 needs to be set to the old d2, which is recorded in s. So we have d1 = s.

    Finally, the return value dp1[n - 1] + dp2[n - 1] is just s + d2.

    The code is as follows.

    class Solution {
    public:
        int numWays(int n, int k) {
            if (n < 2 || !k) return n * k; 
            int s = k, d1 = k, d2 = k * (k - 1); 
            for (int i = 2; i < n; i++) {
                s = d2;
                d2 = (k - 1) * (d1 + d2);
                d1 = s;
            }
            return s + d2;
        }
    };

  • 0
    J

    Thanks for your improvement, it really makes the solution more clear for others to understand, great job!!


  • 0
    L

    why you say "when the color of last two fences (whose indexes are i-1,i-2) are same", why it's not i and i - 1 are the last two fences?


  • 6
    F

    Great stuff. I don't feel this is an easy problem however...


  • 0
    L

    actually, if you know how DP works, it's a easy level. But if you are like me who are just DP beginners, it is hard to figure out the formula, lol


  • 0
    Y

    Why need two-dimensional array?
    Can we use one-dimensional array instead?

    1. Same color for n-1 and n : dp[n] = dp[n-2] *(k-1)
    2. Different color for n-1 and n : dp[n] = dp[n-1] * (k-1)
    

Log in to reply
 

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