动态规划方法的关键点

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

记忆搜索方法和动态规划方法的联系

1、记忆搜索就是某种形态的动态规划方法
2、记忆话搜索方法不关心到达某一个递归过程的的路径，知识单纯地对计算过的递归过程进行记录，避免重复的递归过程
3、动态规划方法则是规定好每一个递归过程的计算顺序，一次进行计算，后面的计算过程严格依赖前面的计算过程
4、两证都是空间换时间的方法，也都有枚举过程，区别就是动态规划规定计算顺序，而记忆搜索不规定

通过例题来说明动态规划问题

• 有value_1、value_2、value_3、……、value_n共n个值，问有几种能构成数aim的组合方式，其中每个value都能使用多次或不用，Aim大于max(value_1, value_2, value3, ……, value_n)
  本题有三种解决方式，即暴力搜索方法、记忆搜索方法、动态规划方法，最容易想到的是暴力搜索方法，通过记忆冗余项的方法优化暴力搜索可以得到记忆搜索方法，而记忆搜索方法本质上也是一种动态规划方法，只不过动态规划方法在记忆搜索优化策略的基础上，规定了计算过程中从简单计算到复杂计算的计算路径，但是这种优化策略的收获是与计算路径无关的，所以记忆搜索方法和动态规划有相同的时间复杂度，即：O(n * Aim²)
  由于动态规划规定了从简单计算到复杂计算的计算路径，就给动态规划进一步优化提供的可能，比如在二维的动态规划问题中dp(value_i, aim)的计算如下：
  
  但是dp(value_i, aim - value_i)的值是已经计算过的简单计算，且正好等于dp(value_(i - 1), 0) + …… + dp(value_(i - 1), aim - 3 * value_i) + dp(value_(i - 1), aim - 2 * value_i) + dp(value_(i - 1), aim - value_i)，所以dp(value_i, aim)的值可以化简为：
  
  由于优化后的算法不需要再枚举很多只，所以动态规划可以优化为时间复杂度为O(n * Aim)
• 有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？
  先列出暴力搜索表达式，其中f(n)表示有n级台阶时的方法数。
  f(i) = f(i - 1) + f(i - 2)，且f(1) = 1, f(2) = 2
  然后根据计算过程中的依赖关系来消除冗余，即可得到动态规划方法
• 给定一个矩阵m，从左上角到右下角移动，每次只能向下走或向右走一步，路径上所有数字的累加和为路径和，返回所有路径中的最小路径和
  这道题如果问有几种方式，就采用组合数来解答，但是要就最小路径和，这个问题满足最优化原理，我们可以用动态规划来解决
  本题为经典的动态规划题目，如果m的大小为M * N，则创建dp矩阵，行数为M，列数为N。dp[i][j]的指标是从左上角，也就是(0, 0)位置，走到(i, j)位置的最短路径和。
  dp中第一行的值为m中从第一行第一个位置到dp中当前位置对应的m中位置的所有数的累加和。
  同理，dp中第一列的值为m中从第一列第一个位置到dp中当前位置对应的m中位置的所有数的累加和。
  那么dp[i][j]的计算方法为：
  1、从dp[i - 1][j]向下到达dp[i][j]
  2、从dp[i][j - 1]向右到达dp[i][j]
  3、从1,2中选择最小的一个再加上当前位置的值就是dp[i][j]的值。
  计算过程中从先从做到右计算一行的值，再从上到下计算下一行的值，最后右下角位置的值即为要求答案
• 给定数组arr，返回arr的最长递增子序列长度，比如arr=[2，1，5，3，6，4，8，9，7]，最长递增子序列为[1，3，4，8，9]，所以返回这个子序列的长度5*
  解答这道题需要申请长度为n的数组dp，dp[i]表示在必须以arr[i]这个数结尾的情况下，arr[0..i]中的最大递增子序列长度。
  1、dp[0] = 1
  2、dp[i] = dp[0..i - 1]中所有满足条件arr[k] < arr[i]的位置k中dp[k]最大的那个数 + 1，即状态方程为：，如果没有满足条件的k存在则dp[i] = 1
• 给定两个字符串str1和str2，返回两个字符串的最长公共子序列。例如，str1="1A2C3D4B56"，str2="B1D23CA45B6A"，"123456“或者“12C4B6“都是最长公共子序列，返回哪一个都行。
  本题为经典的动态规划题目，如果m的大小为M * N，则创建dp矩阵，行数为M，列数为N。dp[i][j]表示str1[0..i]和str2[0..j]中的最长公共子序列的长度。
  dp中第一行的值最大值为1，如果dp[0][j] = str1[0]，则dp[0][j..N]的值都等于1
  dp中第一列的值最大值为1，如果dp[i][0] = str2[0]，则dp[i..M][0]的值都等于1
  那么dp[i][j]的计算方法为：
  1、dp[i][j]可能等于dp[i - 1][j]
  2、dp[i][j]可能等于dp[i][j - 1]
  3、如果str1[i] = str2[j]则dp[i][j]可能等于dp[i - 1][j - 1] + 1
  4、从1,2,3中选择三种可能之的最大值即可
  计算过程中从先从做到右计算一行的值，再从上到下计算下一行的值，最后右下角位置的值即为要求答案
• 有一个承重为w的背包，有N件物品，其重量记在重量数组w中，其价值记在价值数组v中，每件物品可能在背包，也可能不在背包，请在不超过背包承重的前提下返回选出物品的最大价值
  这道题和零钱组合问题的不同有：
  1、零钱组合问题中每个面值的前可以使用0~多次，而背包问题中每个重量的商品物品只能用0或1次
  2、零钱组合问题必须达到目标aim，而背包问题不一定要到承重W
  3、零钱组合为题只是返回组合数即可，背包问题中每件物品都有一定的价值，需要返回某所有问题总价值最大的组合
  解决方法：
  创建大小为N * （W + 1）的的dp矩阵，dp[i][j]表示前i件物品在不超过重量j的前提下的最大价值
  dp中第一行的值：如果j >= w[0]则dp[0][j] = v[0]，否则dp[0][j] = 0
  dp中第一列的值全为0
  下面枚举一下dp[i][j]的情况：
  1、如果选中i件物品放入背包，则前i - 1件物品的总重量不能超过j - w[i]
  2、如果不选i件物品进包，则前i - 1件物品的总重量不能超过j
  3、所以dp[i][j]可能等于dp[i - 1][j]，也可能等于dp[i - 1][j - w[i]] + v[i]，我们从两种可能性中选择最大的那个，即：
  计算过程中从先从做到右计算一行的值，再从上到下计算下一行的值，最后右下角位置的值即为要求答案
• 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别表示插入，删除和替换一个字符的代价，返回将str1编辑成str2的最小代价
  感觉这道题更像零钱组合问题，同样一个操作可以用多次，同样要从一个状态到另一个状态，不过此题要求求出最小代价，而不是单纯地球方案数
  创建大小为(m + 1) * (n + 1)的矩阵dp，dp[i][j]表示从str1[0..i]编辑到str2[0..j]的最小代价
  dp的第一行的值为插入j个值的累积代价
  dp第一列的值为删除j个值的累积代价
  dp[i][j]的值可以从如下4个情况来获得
  1、可能从dp[i - 1][j]的值获得：dp[i][j] = dp[i - 1][j] + dc
  2、可能从dp[i][j - 1]的值获得：dp[i][j] = dp[i][j - 1] + ic
  3、当str1[i - 1] == str2[j - 1]时可能从dp[i - 1][j - 1]的值获得：dp[i][j] = dp[i - 1][j - 1] + rc
  4、当str1[i - 1] != str2[j - 1]时可能从dp[i - 1][j - 1]的值获得：dp[i][j] = dp[i - 1][j - 1]
  可能性中选择最小的那个，即：或
  计算过程中从先从做到右计算一行的值，再从上到下计算下一行的值，最后右下角位置的值即为要求答案