2-Line-Python Recursive With Explanation


  • 0

    Code first:

    class Solution(object):
        def flipLights(self, n, m):
            m, n = min(3, m), min(3, n)
            return 1 if n == 0 or m == 0 else self.flipLights(n - 1,  m) + self.flipLights( n - 1, m - 1)     
    

    Operations: O(flip odds), E(flip evens), A(flip all), T(flip 3k + 1), N(flip nothing)
    Relations:
    O + O = N, E + E = N, A + A = N, T + T = N
    O + E = A, O + A = E, E + A = O
    Exclusive statuses :
    n > 2:
    ① N
    ② O
    ③ E
    ④ A
    ⑤ T
    ⑥ O + T
    ⑦ E + T
    ⑧ A + T

    n = 2 (remove all T related statuses):
    ① N
    ② O
    ③ E
    ④ A

    n = 1(remove all T, E, A related statuses):
    ① N
    ② O

    Steps needed to all status( always can plus 2 * k)
    ① can only be achieved by 0, 2 steps
    ②,③,④ can be achieved by either 1 or 2 steps
    ⑤ can only be achieved by 1 steps
    ⑥,⑦,⑧ can only be achieved by 2 steps,

    Thus:
    0 steps -> ①
    1 steps -> ②,③,④,⑤
    2 steps -> ①,②,③,④,⑥,⑦,⑧
    more than 2 steps -> ①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧

    0_1504741720118_Screen Shot 2017-09-06 at 4.23.25 PM.png

    And now you can notice that value at (y, x) is equal to (y - 1, x) + (y - 1, x - 1).


Log in to reply
 

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