动态规划解题步骤

1. 找出最优解的性质，并刻划其结构特征。《最优子结构》
2. 递归地定义最优值。
3. 以自底向上的方式计算出最优值。
4. 根据计算最优值时得到的信息，构造最优解。

简述：定义最优解、算出最优解、构造最优解
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。（即减小时间复杂度，提升效率）

动态规划算法基本要素是：最优子结构、重叠子问题

最优子结构

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

m<--0
int lookupChain(int i, int j)
{
    if (m[i][j] > 0) 
        return m[i][j];
    if (i == j) 
        return 0;
    int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for (int k = i+1; k < j; k++) 
    {
        int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
        if (t < u) 
            u = t; s[i][j] = k;
    }
    m[i][j] = u;
    return u;
}

经典问题

• 矩阵连乘问题
• 最长公共子序列
• 流水作业调度
• 0-1背包问题
• 最优二叉搜索树

1、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
2、实现最大子段和利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
3、一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
4、用动态规划算法解决最大字段和问题，其时间复杂性为( B ).
A.logn B.n C.n2 D.nlogn
5、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。
6、动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
7、动态规划算法的两个基本要素是. 最优子结构 性质和 重叠子问题 性质。

8、分治法与动态规划法
相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

9、请说明动态规划方法为什么需要最优子结构性质。
答：最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.

10、简述动态规划方法所运用的最优化原理:
“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需要依次作出 n 个决策 D1,D2,…，Dn，如若这个决策序列是最优的，对于任何一个整数 k，1 < k < n，不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策 Dk+1，Dk+2，…，Dn 也是最优的。
动态规划和分治法在分解子问题方面的不同点是:前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的。

11. 动态规划的基本思想
前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；
而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。
不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

12、动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算。实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
（1）分析最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。
总结：动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。

6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

13.备忘录方法是那种算法的变形。（ B ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法

23.下列哪一种算法不是随机化算法（ C ）
A. 蒙特卡罗算法 B. 拉斯维加斯算法 C.动态规划算法 D.舍伍德算法

35．下列是动态规划算法基本要素的是（ D ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质

矩阵连乘问题的算法可由 动态规划 设计实现。

动态规划算法
int MaxSum(int n, int a[])
{
    int sum=0, b=0；   //sum存储当前最大的b[j], b存储b[j]
    for(int j=1； j<=n； j++)  
    {  
        if (b>0)  
            b+= a[j];
        else  
            b=a[i];      空   //一旦某个区段和为负，则从下一个位置累和
        if(b>sum) 
            sum=b;         空
     }
     return sum；
}

1．用动态规划策略求解最长公共子序列问题：
(1)给出计算最优值的递归方程。
(2)给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
答：
(1)
(2)
最长公共子序列：｛ＢＣ｝

8、考虑使用动态规划方法求解下列问题：
01背包数据如下表，求：能够放入背包的最有价值的物品集合。

如设： V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { , } j > wi （不超重）
i在最优子集中 i不在最优子集中

自底向上：按行或列填写下表。

答：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { vi + V(i-1,j-wj) , V(i-1, j) } j > wi （不超重）
i在最优子集中 i不在最优子集中