动态规划

• 动态规划和分治的区别：是否有子问题重复出现
• 动态规划和贪心的区别：
  • 关于最优子结构
    贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
    动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解
  • 关于子问题最优解组合成原问题最优解的组合方式
    贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
    动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案
  • 结果正确性
    贪心不能保证求得的最后解是最佳的，复杂度低
    动态规划本质是穷举法，可以保证结果是最佳的，复杂度高

	分治	动态规划	贪心
适用类型	通用	优化	优化
子问题	每个都不同	很多重复	只有一个
最优子结构	没有要求	必须满足	必须满足
子问题数	全部都要解	全部都要解	只解一个

什么样的递归可以修改为动态规划

• 当一个递归过程中，有重复状态，并且状态与到达目标是没有关系的

动态规划的题解过程

• 定义DP数组的含义
• 定义状态转移方程
• 初始化过程转移的初始值
• 可优化点

线性动态规划

• 线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。
  这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。
  状态定义：
  dp[n] := [0..n] 上问题的解
  状态转移：
  dp[n] = f(dp[n-1], …, dp[0])
  从以上状态定义和状态转移可以看出，大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量 i 表示，i 的大小表示了问题规模的大小，因此从小到大推 i 直至推到 n，就得到了大规模问题的解，这就是线性动态规划的过程。
  按照问题的输入格式，线性动态规划解决的问题主要是单串，双串，矩阵上的问题，因为在单串，双串，矩阵上问题规模可以完全用位置表示，并且位置的大小就是问题规模的大小。因此从前往后推位置就相当于从小到大推问题规模。
  线性动态规划是动态规划中最基本的一类。问题的形式、dp 状态和方程的设计、以及与其它算法的结合上面变化很多。按照 dp 方程中各个维度的含义，可以大致总结出几个主流的问题类型，见后面的小节。除此之外还有很多没有总结进来的变种问题，小众问题，和困难问题，这些问题的解法更多地需要结合自己的做题经验去积累，除此之外，常见的，主流的问题和解法都可以总结成下面的四个小类别。

左程云DP

• 任何动态规划问题都一定对应着一个有重复调用行为的递归

关键点

• 最优化原理，也就是最优子结构性质，这指的是一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优决策，简单来说就是一个最优化策略的子策略总是最优的，如果一个问题满足最优化原理就称其具有最优子结构性质
• 无后效性：指的是某状态下决策的收益，只与状态和决策相关，与到达该状态的方式无关
• 子问题的重叠性，动态规划将原来具有值数级时间复杂度的暴力搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这就是动态规划算法的根本目的。

思路

• 先做出暴力递归的方案
• 接下来分析哪些参数一旦固定，哪些值就可以固定，（哪些结果可以缓存来提高性能）
• 根据前面的参数做出表，
• 表中xy为调用递归的传入参数，
• 初始的传入参数就是在表中最后要求出的参数
• 已经可以得出的函数为递归中的终止条件

实例

• 【 题目】
  给定数组arr， arr中所有的值都为正数且不重复。 每个值代表一种面值的货币， 每种面值的货币可以使用任意张， 再给定一
  个整数aim代表要找的钱数， 求换钱有多少种方法。
  【 举例】
  arr=[5,10,25,1]， aim=0。
  组成0元的方法有1种， 就是所有面值的货币都不用。 所以返回1。
  arr=[5,10,25,1]， aim=15。
  组成15元的方法有6种， 分别为3张5元、 1张10元+1张5元、 1张10元+5张1元、 10张1元+1张5元、 2张5元+5张1元和15张1元。 所以返回6。
  arr=[3,5]， aim=2。任何方法都无法组成2元。 所以返回0

• 暴力递归代码

  /**
      * 暴力递归方法
      *
      * @param arr
      * @param aim
      * @return
      */
     public static int coins1(int[] arr, int aim) {
         if (arr == null || arr.length == 0 || aim < 0) {
             return 0;
         }
         return process1(arr, 0, aim);
     }
   
     /**
      * @param arr
      * @param index 可以任意自由使用index及其之后所有的钱
      * @param aim   目标钱数
      * @return 方法数
      */
     public static int process1(int[] arr, int index, int aim) {
         int res = 0;
         if (index == arr.length) {
             res = aim == 0 ? 1 : 0;
         } else {
             for (int i = 0; arr[index] * i <= aim; i++) {
                 res += process1(arr, index + 1, aim - arr[index] * i);
             }
         }
         return res;
     }

• 建立map二维数组，缓存以前的值

• 动态规划 ，表如图所示

  

  • index表示还剩下多少钱，aim为目标钱数
  • 递归调用时，初始值为0，aim，故需要求出的值为X
  • 递归终止条件为当index=N时，aim== 0 则为1 否则为0，为表中的已知数据
  • 绿色为任意点的值，需要黄色的值来推出

• 代码如下:

  public static int coins3(int[] arr, int aim) {
          if (arr == null || arr.length == 0 || aim < 0) {
              return 0;
          }
          int[][] dp = new int[arr.length][aim + 1];
          //第1列都为0.dp[i][0] 都为1，表示组成钱数0的方法只有1种
          for (int i = 0; i < arr.length; i++) {
              dp[i][0] = 1;
          }
          //第1行中的某些项.dp[0][j]，只使用arr[0]货币，可以组成哪些数
          for (int j = 1; arr[0] * j <= aim; j++) {
              dp[0][arr[0] * j] = 1;
          }
          int num = 0;
          for (int i = 1; i < arr.length; i++) {
              for (int j = 1; j <= aim; j++) {
                  num = 0;
                  for (int k = 0; j - arr[i] * k >= 0; k++) {
                      num += dp[i - 1][j - arr[i] * k];
                  }
                  dp[i][j] = num;
              }
          }
          return dp[arr.length - 1][aim];
      }

• 推出dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]

  public static int coins4(int[] arr, int aim) {
          if (arr == null || arr.length == 0 || aim < 0) {
              return 0;
          }
          int[][] dp = new int[arr.length][aim + 1];
          for (int i = 0; i < arr.length; i++) {
              dp[i][0] = 1;
          }
          for (int j = 1; arr[0] * j <= aim; j++) {
              dp[0][arr[0] * j] = 1;
          }
          for (int i = 1; i < arr.length; i++) {
              for (int j = 1; j <= aim; j++) {
                  dp[i][j] = dp[i - 1][j];
                  dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
              }
          }
          return dp[arr.length - 1][aim];
      }