## basic concept

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.

## key ideas

**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.

## difference to divide and conquer

- 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**

## memoization vs tabulation

- tabulation with
`Fib`

lets you use $O(1)$ space, but memoization with`Fib`

uses $O(N)$ stack space. - example for memo/tabulation: https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-bottom-up-vs-top-down-approaches

## top-down vs bottom up

- usually not distinguish much.

## when to use DP?

满足下面三个条件之一:

- 求最大值最小值
- 判断是否可行
- 统计方案个数

## when NOT to use DP?

- 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$

## DP quartet

- 状态
**State**: 灵感，创造力, what should the hash`dp[]`

stores (`dp[n]`

**usually**stores min/max value) - 方程
**Function**: how to calculate`dp[n]`

based on`dp[n-1]`

,`dp[n-2]`

, ..,`dp[2]`

, and`dp[1]`

- 初始化
**Initialization**: what should the initial values be based on the meaning of the state - 答案
**Answer**: which value should we return as the final result

## DP tips:

- if given string/array have size $N$, usually we need to create a $N+1$ array, where $array[0]$ 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.

## DP vs Greedy Algorithm

Sometimes, DP is not necessary the most optimized solution, greedy could be more efficient than DP

https://leetcode.com/problems/jump-game/description/

Optimized Algorithm: Greedy, time complexity $O(n)$

Sub-optimized Algorithm: DP，time complexity $O(n^2)$

## DP questions:

TODO: lc62: how to brute force all PATHs?

why not recursion?

https://leetcode.com/problems/coin-change/description/

dp could be either solved by**recursive**(divide and conquer + memoization) OR**iterative**approach (nested for-loop)