The Trick to DP

The term Dynamic Programming was tossed by ___. 

Anyway moving forward to DP tricks, reaching a recursive solution to a problem is fairly easy. One gets stuck in applying DP to it or making it iterative. Let's understand it with examples.

Any recursive solution may look like this

def my_recursive_function(self, input, variables) -> int:

#terminating condition

#recursive call 1

#recursive call 2

#.....

#calculating results

#returning the final result 

 

Now variables in any recursive call are of two types

• State variable
• Non-state variables

State Variables: variables that are directly involved in defining or identifying the subproblem. Or in other words, variables which are division factors in dividing a problem into subproblem. Let's be more real and consider the division of India by britishers. What was the division factor? Religion! religion divided the whole india into two. In a similar way for example: 

in the case of Fibonacci, 

f(n) = f(n-1) + f(n-2) 

let's say we write a function for this

def fibonacci(i: int):

if i == 0:

return 0

elif i == 1:

return 1

else:

return fibonacci(i-1) + fibonacci(i-2) 

 

now the function argument 'i' will be a state variable because every i(1,2,3,4,5) is also a subproblem i.e if Fibonacci(5) is the actual problem, then it can be calculated as Fibonacci(4) + Fibonacci(3) where i = 4 and i = 3 are subproblems. So variable which is a subproblem in itself can be considered as a state variable of a problem. It is not necessary that there should be only one such variable, there can be multiple variables and any combination of those variables will be a subproblem. A real world example of two state variables would be 

Also to clearly understand state variables let's understand non-state variables.

Non-state Variables: Let's say we are memorizing the results in our Fibonacci function which will then look like this:

 

def fibonacci(i: int, memo: dict):

if memo.get(i):

return memo[i]

if i == 0:

res = 0

elif i == 1:

res = 1

else:

res = fibonacci(i-1, memo) + fibonacci(i-2, memo)

memo[i] = res

return res

 

Here the variable 'memo' is not playing any role in defining the state of a subproblem like the variable 'i' instead it is only being used to remember the answer of a subproblem so we can say that it is a non-state variable. Now it's time for trick 1:

Trick 1: Minimising and memorizing the state variables - Always try to minimize the state variables. Also for more than two state variables, it is very difficult to write an iterative solution. Actually, this tick also simplifies your solution and helps to memorize it in a more straightforward manner. Always memorize the state variables, for example in our Fibonacci function we have memorized the state variable 'i'. So in a similar fashion, if we have two state variables i and j, our memorizing technique will change to 

memo[i][j] = res or memo[(i,j)] = res, depending upon the type of memo

Calculating Time complexity of a memorized recursive solution: Time complexity in such a case is a product of the sizes of state variables, for example, if there are two state variables i and j having sizes m and n respectively then the time complexity will be of O(m*n). We can reason this because we have memorized state variables which means no combination of state variables can be repeated if it will be repeated it will be used from the memo and hence our recursive function will run for all different combinations of state variables only once.

Trick 2: Trick to memorize a recursive solution: This trick is pretty simple. Let's say we have a recursive solution

 def my_recursive_function(state_variable_1,

state_variable_2, non_state_variables...) -> int:

#terminating condition

#recursive call 1

#recursive call 2

#.....

#calculating results

#returning the final result

 

 to memorize the above solution we can always do. 

def my_recursive_function(state_variable_1,

state_variable_2, non_state_variable, memo:dict) -> int:

if memo.get((state_variable_1, state_variable_2)):

return memo[state_variable_1,state_variable_2]

#terminating condition

#recursive call 1

#recursive call 2

#.....

#calculating final result

memo[state_variable_1,state_variable_2] = final result

#returning the final result

Also, it is not always guaranteed that memorizing a recursive solution will

optimize the solution. It depends on how much you can minimize the state variables.