Dynamic Programming

Description

These flash cards have the most common DP problems and their hints.
Subash M
Flashcards by Subash M, updated more than 1 year ago
Subash M
Created by Subash M over 6 years ago
14
0

Resource summary

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
Show full summary Hide full summary

Similar

Fuzzy Logic and Its Uses - Multiple Choice Questions
Md. Saifuddin Khalid
Dijkstra's Shortest Path
Josh Calvert
Apendicitis
nestormondragon .
Computing - Chapter one summary -
Beenish Shabir
Video Revision
Mr Mckinlay
Fundamentals of Algorithms
Jemima Orakwue
MM-Data Structures & Algs Course Content
Eithne O'Sullivan
Algorithm set 3
Harry Clements
Algorithm analysis
musi900
Kruskal's Algorithm Flashcards
Ezra Dorland