01、动态规划

思想大于代码

最好把图画出来，把动态矩阵画出来分析。

SubSets

binary search Tree

一维 dp[i]代表[0,i)的答案

爬楼梯问题：dp(i)=dp(i-1)+dp(i-2)

二维dp[i][j]代表array[i]~array[j]这段subarray的答案

1. 2D数组

   机器人路径问题：dp(i,j)=Max(dp(i-1,j)+Vij,dp(i,j-1)+Vij)

2. 2个1D数组

3. 1D数组的2D状态

   子串问题

4. 1D数组+k

   三维 几步之内

2Darray+K

适用的问题

最优解列举

打家劫舍

计算出所有的OPT(i)，带入列举的所有方案得到最优解

为什么用动态规划

• DP是枚举有希望成为答案的解。这个空间比暴力的小得多。
• DP的核心思想：尽量缩小可能解空间。
• 我们的算法都是在可能解空间内，寻找最优解。空间换时间
• 在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。
• 动态规划是将递归转为非递归的？？？

  分析步骤

1. 判断是否可用
2. 状态转移方程
3. 边界分析，作为初始化数组的值。
4. 填表
5. 读表得结果

   代码步骤

• 用二维数组保存所有中间结果———数组的设置？列 为给定值，行 为目标值和中间结果
• 计算出递归的所有出口条件到数组—-初始化数组
• 用循环代替递归过程——-下面一行的结果，由上面一行的值（结果）得到。填充所有数组的值。
• 最终结果，来自于问题，也就是最大下标的数组元素（右下角）的值。

  判断量是什么？

  前一个最佳方案√选还是不选
  当前位置的元素对结果的影响×这个属于后面（最大和）如果成立去的是尾，动态规划要去头。