Dynamic Programming

Especially used to solve the problems seems need O(2^n) or O(n!) and produce polynomial-time O(n^2) algorithms

Difference with Divide-Conquer

Divide-Conquer: partition the problem into disjoint subproblems. Solve them recursively and then combine their solutions to solve the original problem.

Dynamic Programming: Subproblems overlap. Subproblems will share subproblems. In this context, divide-conquer does more work than necessary. But DP solve the problem only once, save the answers in a table.

Four Main Factors of DP(DP四要素)

Subproblem: Understand what is the subproblem which can lead to the final answer of the DP problem. Always in same expression of big problem. (搞清楚子问题是什么，DP中子问题往往与最终答案拥有相同形式， 较为直观)

Function: How to get final answer by the subproblems

Initialization: Initialize the most basic subproblem.(对最极限的子问题进行初始化，问题起点；同时对无法有效涵盖入Function的子问题初始化，如二维数组的边界点)

Answer: The answer of the big problem. Think clear how to obtain it, not always in the final position!!!(最终问题的答案，不一定只出现在最后的位置！！！)

When to Dynamic Programming

Encounter following three situations, great possibility to use dynamic programming.

1. Optimization problems: Find the maximum and minimum(找寻最大最小值)

2. Decide if have solutions(判断是否可行)

3. Return the number of possible solutions(统计方案个数)

When Not to use Dynamic Programming

• Need to find out all the possible solutions rather than a number, usually use DFS (要求具体方案而不是可行方案个数)

• Input is a set rather than a sequence (输入数据是一个集合而不是序列)