9. Dynamic Programming

Refs:

• MIT 6.006 Spring 11, lecture 18, 19, 20
• MIT 6.046 Spring 15, lecture 10

One-dimensional Optimization

LC 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Two-dimentional

distinc subseq

Solution: http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation

LC 139 Word Break

Knapsack Problems