This is my simple recursive code - Either put word on same line, or on new line:
def justify_(i, spaces):
if i == len(words):
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.
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 ?
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 ?