理念

切分子问题，同时记住已经解决过的子问题的解，以便解决整个问题。
适用场景： 重叠子问题，和最优子结构
下面以例子来解释

钢管切割问题

本题是算法导论上的题目具体问题不描述，直接复制粘贴来：
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。

1552533538818-e99b00cf-29bc-4602-a729-2b7a95c59f66.png
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

问题分析与实现，首先简单暴力的来一个：

暴力递归解法

先来个公式： rn = Max(pi, r(n-i)) 0 =< i <= n
这个公式是怎么得到的？

r2 

  1. function CutRod(pn=[], n) {
  2.   if (n === 0) return 0;
  3.   let q = pn[0];
  4.   let f = 0;
  5.   for(let i = 1 ; i < n ; i++){
  6.     f = Math.max(pn[n-1], CutRod(p, i) + CutRod(p, n-i));
  7.     q = Math.max(f, q);
  8.   }
  9.   return q
  10. }

动态规划-自顶向下

此处又分为两种自顶向下的递归，只是带了备忘记录。比纯暴力解法省下了很多计算

  1. function MemoizedCutRodAux(pn, n, r) {
  2.   if(r[n]) return r[n]
  3.   let q = -1;
  4.   if(n === 0) q = 0;
  5.   else {
  6.     for(let i = 1 ; i < n ; i++){
  7.       let tmp = pn[i-1] + MemoizedCutRodAux(pn, n-i, r)
  8.       if( q < tmp) q = tmp
  9.     }
  10.   }
  11.   r[n] = q;
  12.   return r[n]
  13. }
  14. function MemoizedCutRod(pn=[], n) {
  15.   let r = []
  16.   for(let i = 0 ; i < n ; i ++) {
  17.     r[i] = -1
  18.   }
  19.   return MemoizedCutRodAux(pn, n, r)
  20. }

动态规划-自底向上

  1. function BottomUpCutRod(pn=[], n) {
  2.   let r = new Array(n)
  3.   r[0] = 0
  4.   for(let i = 1 ; i < n ; i ++) {
  5.     let q = -1
  6.     for(let j = 1; j < i; j ++) {
  7.       let tmp = p[j] + r[i - j];
  8.       if(q > tmp) q = tmp
  9.     }
  10.     r[i] = q
  11.   }
  12.   return r[n]
  13. }