A complex problem can be break into multiple subproblem, hope for subproblem is easy enough so that it could be easily solved. Memeorziation is part of DP which helps to reduce unnecessary computation.
- recursion tree: draw out for subproblem
- memoization: cache duplicate sub-steps (result of overlap subproblems)
- dynamic programing = recursion(divide & conquer) + memoization
- dp 是一种设计的思想 不是一种算法
DP can be implemented via two ways:
- recursively (recursion + memoization)
- itratively (forloop OR nested forloops)
Iterative algorithm can also utilize DP
iterative approach usually faster, but harder to construct.
recursive approach also call ‘lazy approach’, if ‘lazy’ not too bad, we tend to stick with it since it is easy to reasoning.
- subproblems between dynmaically programming are NOT independent, solution of current subproblem usually depends on result of previous states
- on the other hand, subproblems in divide and conquer are usually independent
- tabulation with
Fiblets you use $O(1)$ space, but memoization with
Fibuses $O(N)$ stack space.
- example for memo/tabulation: https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-bottom-up-vs-top-down-approaches
- usually not distinguish much.
- ask for all possible paths, instead of number of paths
- 输入数据是一个 集合 而不是 序列???
- 暴力算法的复杂度已经是多项式($n^2,n^3$)级别: 动态规划擅长与优化指数级别复杂度($2^n,n!$)到多项式级别复杂度($n^2,n^3$), 不擅长优化$n^3$到$n^2$
- 状态 State: 灵感，创造力, what should the hash
dp[n]usually stores min/max value)
- 方程 Function: how to calculate
- 初始化 Initialization: what should the initial values be based on the meaning of the state
- 答案 Answer: which value should we return as the final result
- if given string/array have size $N$, usually we need to create a $N+1$ array, where $array$ for initialization.
- if given 2D array with size $m$ and $n$, usually we create a new $hash[m][n]$ 2D array. Try $hahs[m+1][n+1]$ if $hash[m][n]$ not work.
Sometimes, DP is not necessary the most optimized solution, greedy could be more efficient than DP
Optimized Algorithm: Greedy, time complexity $O(n)$
Sub-optimized Algorithm: DP，time complexity $O(n^2)$
TODO: lc62: how to brute force all PATHs?
why not recursion?
dp could be either solved by recursive (divide and conquer + memoization) OR iterative approach (nested for-loop)