DP with only plus operator in Python


  • 0
    L

    Observe that
    [0]
    [0, 1] = [0, 0+1]
    [0, 1, 1, 2] = [0, 1, 0+1, 1+1]
    [0, 1, 1, 2, 1, 2, 2, 3] = [0, 1, 1, 2, 0+1, 1+1, 1+1, 2+1]
    One can do this without bit operation, division, or % operator.

    def countBits(self, num):
        out = [0]*(num + 1)
        jmax = 0
        j = 0
        for i in xrange(1, num + 1):
            out[i] = 1 + out[j]
            if j == jmax: #if j hit the current repeat maximum
                jmax = i
                j = 0
            else:
                j += 1
        return out
    

Log in to reply
 

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