动态规划
通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有
重叠子问题和最优子结构性质的问题。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
适用条件：
- 重叠子问题：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
- 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质
- 无后效性：即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
动态规划的核心是记住子问题解，一般有两种方式：
- 自顶向下的备忘录：
递归+备忘录public static int Fibonacci(int n) { if(n<=0) return n; int []Memo=new int[n+1]; for(int i=0;i<=n;i++) Memo[i]=-1; return fib(n, Memo); } public static int fib(int n,int []Memo) { if(Memo[n]!=-1) return Memo[n]; //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。 if(n<=2) Memo[n]=1; else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo); return Memo[n]; } - 自底向上的循环：
循环+备忘录public static int fib(int n) { if(n<=0) return n; int []Memo=new int[n+1]; Memo[0]=0; Memo[1]=1; for(int i=2;i<=n;i++) { Memo[i]=Memo[i-1]+Memo[i-2]; } return Memo[n]; }
求解过程：
- 定义子问题
- 定义状态转移方程
- 定义边界值
动态规划和分治法很相似
- 分治法是指将问题分成一些独立的子问题，递归的求解各子问题
- 动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题，通过使用
备忘录保存中间结果来避免子问题的重复求值
动态规划和贪心算法
背包问题
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
| 则其状态转移方程便是：dp[i][j] = max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j]) ({i,j | 0<i<=N,0<=j<=M}) |
状态转移分以下几种情况：
-
边界: dp[i][j] = 0, (i = 0 j = 0) - 第 i 件比总重大: dp[i][j] = dp[i - 1][j], (weight[i] > W)
- 在放完前 n - 1 件后，第 i 件物品放不下: dp[i][j] = dp[i-1][j]
- 在放完前 n - 1 件后，第 i 件物品放得下: dp[i][j] = dp[i-1][j - weight[i]] + value[i]
边界是：
所以，算法实现如下：
for(let i=0; i< N; i++)
dp[i][0] = 0
for(let j=0; j< M; j++)
dp[0][j] = 0
for(let i = 1; i < N; i++) {
for(let j = 0; j< W; j++) {
if(weight[i] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}
}
