(Python) 16.11 Pretty Printing Problem - Recursion Time Complexity, and Conversion to DP?

#1

This is my simple recursive code - Either put word on same line, or on new line:

def justify_(i, spaces):
if i == len(words):
return spaces**2

else:
    return min(
        justify_( i+1, spaces - (1+len(words[i])) ) if 1 + len(words[i]) <= spaces else float('inf'),   # same line
        spaces**2 + justify_( i+1, maxWidth-len(words[i]) )   # new line
    )

I can then cache results to avoid repetitions. I find this approach intuitive.

  1. How to find time complexity of this ?
    Tn = 2Tn-1 + 1 ? That’s exponential 2^n. But what if we cache results, then what’s complexity ?

  2. How to get intuition for converting this to Dynamic Programming - what are the variables to use in For loops ? I’m not asking for book’s method… but given above recurrence, how to convert to DP ?

0 Likes