Explanation of DP, O(n) time complexity, O(1) space complexity


  • 15
    T

    Given an 'n', there are two kinds of color combinations.

    1. The last two colors are the same, which is denoted as fsame in my code.
    2. The last two colors are different, which is denoted as fdiff in my code.

    Now consider 'n+1' and its two kinds of solutions.

    1. Regarding case 1, the new fsame equals the old fdiff, right? Otherwise, there would be three adjacent walls with the same color.
    2. Regarding case 2, all old combinations with length 'n' are legally combined with one of remaining (k-1) colors.

    So the update formula is

    1. fsame(n + 1) = fdiff(n)
    2. fdiff(n + 1) = (fsame(n) + fdiff(n)) * (k - 1)

    As no need to keep all history of fsame and fdiff, so the space complexity is O(1). The code is as follows.

    class Solution {
     public:
      int numWays(int n, int k) {
        if (n == 0) {
          return 0;
        }
        if (n == 1) {
          return k;
        }
        if (n == 2) {
          return k * k;
        }
    
        // fsame(n): the number of combs, whose last digits are the same.
        // fdiff(n): the number of combs, whose last digits are different.
        int fsame = k, fdiff = k * (k - 1);
        for (int p = 3; p <= n; ++p) {
          auto fsame1 = fdiff;
          auto fdiff1 = (fsame + fdiff) * (k - 1);
          fsame = fsame1;
          fdiff = fdiff1;
        }
    
        return fsame + fdiff;
      }
    };
    

    Tian Xia


  • 0
    I

    Great solution and thanks for the explanation. Could you explain a little how you came to recognize that the key was to differentiate whether the last two colors were the same or different?


  • 0
    I

    I think he got that from the rule that u can't have more than 2 adj fences with same color


  • 0
    L

    I so don't understand this


Log in to reply
 

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