Introduction
Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly ‘Remember your Past’) . If the given problem can be broken up into smaller subproblems and these smaller subproblems can be in turn divided in to stillsmaller ones, and in this process, if you observe some overlappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem.
major points
 can be divided into smaller subproblems
 there are strong overlapping among subproblems
typical methods
There are two ways of doing this.
 TopDown : Start solving the given problem by breaking it down. If you see that the problem has been solved already (different from the predefined value), then just return the saved answer. If it has not been solved, solve it and save the answer. This is referred to as Memoization.
 BottomUp : Analyze the problem and see the order in which the subproblems are solved and start solving from the trivial subproblems, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.
difference with divide and conquer
Note that divide and conquer is slightly a different technique. In that, we divide the problem in to nonoverlapping subproblems and solve them independently
, like in merge sort and quick sort.
friendship with greedy
Complementary to Dynamic Programming are Greedy Algorithms which make a decision once and for all every time they need to make a choice, in such a way that it leads to a nearoptimal solution. A Dynamic Programming solution is based on the principal of Mathematical Induction greedy algorithms require other kinds of proof.
Examples
Even some of the highrated coders go wrong in tricky DP problems many times. DP gurus suggest that DP is an art and its all about Practice
. The more DP problems you solve, the easier it gets to relate a new problem to the one you solved already and tune your thinking very fast. It looks like a magic when you see some one solving a tricky DP so easily.
Maximal Square
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.


House Robber II
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of nonnegative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.


Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,2,4],
the contiguous subarray [2,3] has the largest product = 6.




Classic
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.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Typical DP solution


But actually we can do much better using window
in which if we manually implement the lower_bound
via binary search we can achieve further better.


Minimum Path Sum
Given a m x n grid filled with nonnegative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.


Longest Common Subsequence (LCS)
Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Here is an example:
S = “rabbbit”, T = “rabbit”
Return 3.


Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”, s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.


Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character


Wildcard Matching
Implement wildcard pattern matching with support for ‘?’ and ‘*’.
 ‘?’ Matches any single character.
 ‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, ““) → true
isMatch(“aa”, “a“) → true
isMatch(“ab”, “?“) → true
isMatch(“aab”, “ca*b”) → false


Sometimes there are just funny solutions to complicated problems as follows, quite intuitive and efficient.


Regular Expression Matching
Implement regular expression matching with support for ‘.’ and ‘*’.
 ‘.’ Matches any single character.
 ‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “ca*b”) → true


A simple DFS solution can be quite efficient in this case.


Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (wellformed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.


Integrated problems
These problems are not just about DP any more, they will cover greedy, backtracking, math and sometimes even some original tricks. Have fun here…
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
For example, given s = “aab”,
Return
[
[“aa”,”b”],
[“a”,”a”,”b”]
]
Using DP to accelerate the backtracking  typical integrated problem


Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].
A solution is [“cats and dog”, “cat sand dog”].
Using DP to accelerate the backtracking  typical integrated problem


Burst Balloons
Given n balloons, indexed from 0 to n1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imagine nums[1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8] Return 167
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167


Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two nonempty substrings recursively.
Below is one possible representation of s1 = “great”:
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any nonleaf node and swap its two children.
For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that “rgeat” is a scrambled string of “great”.
Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that “rgtae” is a scrambled string of “great”.
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Quite typical DP solution but we have to transferring this problem into proper forms first.


Another backtracking solution considering symmetric features of the scrambled string.


Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine.
Example 1: nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2: nums: [1,2,4,8]
Result: [1,2,4,8]


Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Typical DP solution


But actually there is a math solution which can be pretty simple and clean as Lagrange’s foursquare theorem whose formula will be 4^k(8m+7) if there are four squares to make up the number.


Create Maximum Number
Given two arrays of length m and n with digits 09 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]


This solution can be further optimized…
Always welcome new ideas and practical tricks, just leave them in the comments!