Skip to main content

dynamic-prog

Dynamic Programming#

  • lookup, cache variable names

  • we can use hash map for lookup also , just like in calculating fibancci

  • start by breaking a big problem and use chunking. e.g for a problem on array start with one lement, then add one more and solve, then add one more an soleve and then develop logic

  • first write the logic possibly in recusrsion, and check if there is any ocerlapping

  • If last characters of both sequences match (or X[m-1] == Y[n-1]) then

L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
  • If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then 
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) )

  • Create a 2D array for lookup when necessary

  • first think from top bottom approach and write the recurson.

  • maxOf(whenItemSelected, whenItemNotSelected) - do recusrion using this. Knapsack problem

  • whenevenr required you may create a hashmap lookup; possible 2d array represenation of hash map. e.g cache = { 0 : { 45: 2, 32: 1 }, 1: { 25: 1, 32: 4 } }

  • run a for loop, and cover all the possibilities and each iteration use recusrion to collect all the possible coount and then at the end decide the max or min accordingly . e.g Palindrome Partitioning

  for(int k = i; k < j; k++){    count = minPalPartion(String, i, k) + minPalPartion(String, k + 1, j) + 1;    ans = min(ans, count);  }
  • There are many applocation of LIS problem - (Just need to modify the criteria from length to accordingly) sort the list, and then apply the LIS algorithm Box stacking problem, Maximum sum increasing subsequence, Maximum Length Chain of Pairs