Dynamic Drogramming

Dynamic Programming

Generally used in optimization problem where you trivially do an exhaustive search of all possible solutions

What is DP

• careful brute force
• sub-problem + “reuse” : Take the problem at hand, find sub-problems, solve those sub-problems and re-use those solution to solve the actual problem
• memoize (remember solution) and “reuse” solutions of sub-problems
• computing shortest path in DAG of subproblem dependency

Steps

• define subproblems and count number of subproblems
• guess part of the solution and count number of choices
• relate subproblem solution & calculate time per sub-problem
• (recursion+memoization or iteratively-bottom-up approach)
• solve the original problem
• use parent pointers to get the answer

Problems

• Fibonacci Numbers
• Text Justification
• Longest Common sub-Sequence
• Paranthesization - matrix sequence multiplication
• Largest Divisible Subset
• Stone Smashing Problem
• Longest Common Subsequence