动态规划

动态规划的基本步骤

1. 分析最优子结构

• 找出最优解的性质，并刻画其结构特征

2. 建立递归关系

• 递归地定义最优值

3. 计算最优值

• 以自底向上的方式计算出最优值（分治相反）

4. 构造最优解

• 根据计算最优值时得到的信息

动态规划：

• 把小问题的解存储起来，大问题的最优解一定是小问题的最优解得出，而分治法则不同。

动态规划的基本要素

• 最优子结构

• 重叠子问题（子问题独立则用分治法）

动态规划例子

矩阵连乘

矩阵的维数分别为： A1: 5☓2，A2: 2☓4，A3: 4☓3，A4: 3☓5 给出用动态规划算法解决该问题时矩阵m(n行，n列)和s(n行，n列)的值 给出矩阵A1A2A3A4连乘的最小数乘次数以及计算顺序（用加括号的方式表示）

• m[1][4]=104：表示A1A2A3A4连乘的最小值为104
• s[1][4]=1：表示A1A2A3A4连乘的最小值的划分为A1(A2A3A4)
• A1(A2A3)= m[1][3] ：m[1][1] + m[2][3] + A1乘（A2A3连乘后的行列）的值

0-1背包问题

问题：假设背包容量为5。共有3种物品，其重量w={1, 2, 3}，价值v={6, 10, 2}，选择哪几个物品装入背包中，使得背包中物品的价值最大？ 要求： 给出用动态规划法解决上面背包问题时的矩阵m(n+1行，C+1列)及向量x(n行，1列) 给出最优值（背包中物品的最大价值）及最优解（放入背包中的物品）

最长公共子序列

求序列X={1, 2, 4, 6}和Y={2, 6, 4, 8}的最长公共子序列长度以及最长公共子序列 并给出用动态规划解决问题时矩阵c(m+1行，n+1列)和b(m行，n列)

解题步骤： ps：某元素的对角线位为”1“号位，上面为”2“号位，左边为”3“号位

1. 比较某位置的行和列元素，若相等则取1号位置（对角线）的值 + 1，若不相等，则取2号位（上面）和3号位（左边）的最大值（2号和3号位的相等则默认取2号的）。

2. 第二张表则填取的是几号位的，最后从表的右下角开始，根据是从几号位的获取的值逆着走，如2则往上走，3则往左走，最后得到的路径中是1的所对应的值就是最长公共子序列。

最大字段和

求序列{5, 2, -4, -8, 3, 4, 1}的最大字段和及相应的最大字段 给出用动态规划法求最大字段和的向量b(1行，n列)

答题步骤：

1. b的值为该位置前面的数字的总和，若为负数，则填0
2. 找到最大的值，则取其位置到前面b的值为0的位置的所有对应的数字

最大子段和：8 最大子段{3, 4, 1}