Dynamic Programming

Question	Answer
Find Longest Common Substring	Longest Common Suffix of all the Substrings ToDo: Tabulation and if same char, increment diagonal and place in current position
Longest Increasing Subsequence	O(n^2) 1) Iterate i and bring j from beginning 2) Get Maximum length & a[j] < a[i] 3) MaxLen + 1 OR 1 4) Max of final array is answer
LIS O(nlogn)	1) S - Active Array, R - for Path, Len 2) Each index of S- Smallest element of that Size. A[0] = smallest 1 digit element 3) First check last index, if greater, new element in S 4) If less than first element, replace first element 5) Do CeilIndex search over middle elements.
Fibonacci	1) Memoization 2) Power of Matrix "M" \|F(n+1) F(n) \| \| F(n) F(n-1) \| Power(M, n-1) => M[0,0] = F(n) Use Pow(M, n) Optimization for O(log n)
0-1 Knapsack	1) Do tabulation for different weights and [0, 1... TotalWeight] 2) If current weight <= j (linear dist of TotWeight) add profit 3) If not, copy value from previous weight iteration O(nW)
Longest Common SubSequence	1) Retain the maximum length so far. 2) Take an example and check tabulation. http://ide.geeksforgeeks.org/nGQR66

Resource summary

	Created by Subash M over 7 years ago