动态规划的递归写法与递推写法

  多训练，多思考，多总结是学习动态规划的重点

什么是动态规划

  动态规划是一种用来解决一类最优化问题的算法思想
  一般可以使用递归或递推的写法来实现动态规划

动态规划的递归写法

  如果一个问题可被分解为若干子问题［分治］
  且子问题会重复出现［重叠子问题］
  动态规划下，记录问题的解答，使得下次碰到相同的子问题时直接使用之前记录的结果，避免不必要的重复计算［算法性能优化策略］

动态规划的递推写法

  将一些数字排成数塔的形状
  其中第一层有一个数字，
  第二层有两个数字，
  ．．．
  第ｎ层有ｎ个数字
  现在要从第一层走到第ｎ层
  每次只能走向下一层连接的两个数字中的一个
  问：
  最后将路径上所有数字相加后得到的和最大是多少？
  

  如开一个二维数组ｆ
  其中f[i][j]存放ｉ层的第ｊ个数字
  不妨令dp[i][j]表示从第ｉ行第ｊ个数字出发的到达最底层的所有路径中能得到的最大和
  定义了这个数组后dp[1][1]就是最终想要的答案
  dp[1][1]=max(dp[2][1], dp[2][2]) + f[1][1]

  d[i][j]=max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
  把dp[i][j]称为问题的状态，把上面的式子称作状态转移方程

  数塔的最后一层的dp值总是等于元素本身
  即dp[n][j]==f[n][j](1<=j<=n)
  把这种可直接确定结果的部分叫边界
  动态规划的递推写法总是从这些边界出发，通过状态转移方程扩散到整个dp数组
  

  如果一个问题的最优解可由子问题最优解构造，称有最优子结构
  最优子结构［最优化的分治］
  重叠子问题［效率优化的凭借］
  -->效率优化的最优化分治＝动态规划

  贪心：
  是某些最优子结构＋重叠子问题情形，
  可证明，每一次可作特定选择，结合一个子问题得到原问题的解答，
  属于依据问题性质，只处理部分而得到结果的情况．［更强的效率优化］

最大连续子序列和

  给定一个数字序列A_{1}, A_{2}, ... , A_{n}
  求i, j(1 <= i <= j <= n)
  使得A_{i}+...+A_{j}最大
  输出这个最大和

  －　令状态dp[i]表示以A[i]作为末尾的连续序列的最大和［这里说A[i]必须作为连续序列的末尾］
  通过设置这么一个dp数组，要求的最大和其实就是dp[0], dp[1], ... , dp[n-1]中的最大值
  －　作如下考虑
  因为dp[i]要求必须以A[i]结尾的连续序列
  则只有两种情况
  １，这个最大和的连续序列只有一个元素，即以A[i]开始，以A[i]结尾
  ２，这个最大和的连续序列有多个元素，即从前面某处A[p]开始(p < i)，
  一直到A[i]结尾
  对第一种情况，最大和就是A[i]本身
  对第二种情况，最大和是dp[i-1]+A[i]，即A[p]+...+A[i-1]+A[i]=dp[i-1]+A[i]
  由于只有这两种情况，于是得到状态转移方程
  dp[i]=max{A[i], dp[i-1]+A[i]}
  且边界为dp[0]=A[0]
  由此从小到大枚举ｉ，即可得到整个dp数组
  接着输出dp[0],...,dp[n-1]中的最大值即为最大连续子序列的和

  状态无后效性是指：
  当前状态记录了历史信息，
  一旦当前状态确定，
  就不会再改变
  且未来的决策只能在已有的一个或若干个状态的基础上进行
  历史信息只能通过已有的状态去影响未来的决策

  设计状态和状态转移方程是动态规划的关键

最长不下降子序列［ＬＩＳ］

  在一个数字序列中，
  找到一个最长的子序列［可以不连续］
  使得这个子序列是不下降的［非递减的］

  令dp[i]表示以A[i]结尾的最长不下降子序列长度
  这样对A[i]来说会有两种可能
  －　如存在A[i]之前的元素A[j](j < i)
  使得A[

提高篇－－动态规划专题

原文：https://www.cnblogs.com/raindayinrain/p/13694053.html