对于动态规划思想的理解

1. 问题是求某个最优解
2. 问题具有最优子结构性质，即状态dp(n)的最优解有赖于dp(n - k)的最优解，n状态根据子问题根据子问题最优解做出的决策就是最优的，不用考虑后续的状态，
3. 从问题某个状态向下考虑，采用不同的策略可以拆成重叠的子问题

动态规划在题目中的作用很大程度是遍历所有结果，并且省去很多不用再次遍历的情况，最后从“遍历的所有结果”中找到最优。下面介绍动态规划两种方法。

从最开始的状态开始，不同的决策最后会造成不同的系统状态。这样的想法像一个二叉树一样，下图展示的是每个状态有两种决策的情况，可以看出这样的方法在写程序的时候可以考虑递归完成。

图中展示了每个状态通过不同的决策最后达到“叶子节点”（这并不是一个真的二叉树，挪用叶子节点的概念表达系统的最后一个状态）。这里可以看出问题有重复子结构，例如当element[0]做出决策后，element[1]会通过会继续想下做决策，最后返回给element[0]的决策者一个以element[1]当前状态为起始的最优解。当element[0]再次做出决策2时，因为问题具有最优子结构，会发现这时需要的就是element[1]为起始的最优解，而这个最优解已经在这个二叉树左侧分支计算过了，这时直接用这个最优解就可以了。这个最优解可以通过“记忆簿”记录下来。而element[0]就可以比较决策1和2哪个最优了。

自底向上是动态规划最常用的方法，个人认为效率自上而下的方法下率高。
从最简单的子结构开始（n=1），思考当问题变得复杂的时候（n=2,3,…i），最佳解决方案是什么。之前子问题的最优解等信息加上当前决策得到当前最优解，这个过程需要根据题目自己得出的状态转移方程。这样就可一直计算到n = N，得到整体最优解（这是问题具有最优子结构的性质）。如下图，从element[3],也就是”叶子节点“开始，这个只有一个元素的情况下可以很直观的得到答案，接着假设element[2]根据element[3]得到自己的最优决策是决策1，这样，{element[2],element[3]}这个问题的最优就得到了。

红色的线表明该状态根据前面的状态做出的最优决策（具体什么决策是假设），最后得到整体最优解为，决策1->决策2->决策1->叶子节点决策。

1. 题目
   公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。
   

2. 题目分析
   一根长n英寸的钢条有2^(n-1)种切割方法，即在每个一英寸处可以选择切割或者不切割，暴力解法是把所有情况都遍历一遍，这样的话就是O(2^n)的时间复杂度，这样显然不可取。现在分析这个问题，首先，这个问题是求某个最优解也就是最大收益；其次，这个问题有最优子结构性质，一个长度n的钢条可以根据n-1，n-2…1这些子情况得出最优解，且当前决策做出的最优解最后会转移成整个问题的最优解，不用考虑n+1得情况；最后，该问题有重叠子问题，第i点切不切都要面对相同的子问题。由此，这道题可以通过动态规划求解，其递归方程：Rn = ∑(i:1->n)max（Pi + Rn-i）。
   下图是这个题目的模型，节点内容表示钢条长度：
   

3. 代码实现（C++）
   自上而下带记忆簿的方法

   int MemoizedCutRodAux(const int *p, int n, int *r)
   {
       if (r[n] >= 0) //数组r是记忆簿，初始的每个值都为-1
       {
           return r[n];
       }
       int q = -1;
       if (n == 0)
       {
           q = 0;
       }
       else
       {
           for (int i = 1; i <= n; ++i) //在每个i选择切割和不切割，并递归剩下的长度得到最优解
           {
               int tmp = p[i] + MemoizedCutRodAux(p, n - i, r);
               if (q < tmp)
               {
                   q = tmp;
               }
           }
       }
       r[n] = q;
       return q;
   }

自底向上的动态规划

int BottomUp(int n, int* p)
{
    for (int i = 1; i < n + 1; i++)
    {
        int tempMaxPrice = 0;
        for (int j = 1; j <= i; j++) //下面取得钢条长度为i的时候的最大收益
        {
            int maxPrice = p[j] + result[i - j];
            if (maxPrice > tempMaxPrice)
            {
                tempMaxPrice = maxPrice;
            }
        }
        result[i] = tempMaxPrice;
    }
    return result[n];
}