计算机算法：动态规划的概念、核心要素与经典问题（详细分析与总结）_动态规划问题用什么求解

目录

动态规划的概念

动态规划的核心要素

动态规划的经典问题

切割钢条

爬楼梯

01背包问题

最长公共子序列/最长回文子序列

---

动态规划的概念

动态规划方法通常用来求解最优化问题（optimization problem)。这类问题可以有很多可解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解（an optimal solution),而不是最优解（the optimal solution),因为可能有多个解都达到最优值。

动态规划适用于子问题重叠的情况，也就是不同的子问题存在公共的子子问题。在这种情况下，分治算法会进行很多次不必要的工作，而动态规划只计算一次，将其解保存在一个矩阵中，从而避免了不必要的重复计算。

我们通常按如下4个步骤来设计一个动态规划算法：

1.刻画一个最优解的结构特征。

2.递归地定义最优解的值。

3.计算最优解的值，通常采用自底向上的方法。

4.利用计算出的信息构造一个最优解。

步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4,有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构造一个最优解。

动态规划的核心要素

最优子结构和子问题重叠

用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个好线索（当然，具有最优子结构性质也可能意味着适合应用贪心策略）。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解。因此，我们必须小心确保考察了最优解中用到的所有子问题。

适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同子问题的总数是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题（overlapping subproblems)性质。

在我看来，动态规划实质上，是状态与选择的问题。

首先明确最终的问题是什么。在最终问题中提取出问题状态，从而确定子问题。这里的状态决定了问题是子问题还是最终问题！

我们一般定义：dp[状态1][状态2][状态3]表示需要最优化的值

状态转移方程：当前值=最优的(选择1，选择2，选择3...)

动态规划的经典问题

切割钢条

钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,...,n)，求切割钢条方案，使得销售收益rn最大。

注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

长度为n英寸的钢条共有2一种不同的切割方案，因为在距离钢条左端i(i=1,2,…，n-1)英寸处，我们总是可以选择切割或不切割。我们用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7英寸的钢条切割为三段——两段长度为2英寸、一段长度为3英寸。如果一个最优解将钢条切割为k段（对某个1≤k≤n),那么最优切割方案n=i1+i2+...+ik将钢条切割为长度分别为i1,i2,i3,…,ik的小段，得到最大收益rn=p(i1)+p(i2)+...+p(in)。

对于上述价格表样例，我们可以观察所有最优收益值ri(i=1,2,…，10)及对应的最优切割方案：
r1=1,切割方案1=1(无切割）
r2=5,切割方案2=2(无切割）
r3=8,切割方案3=3(无切割）
r4=10,切割方案4=2+2
rs=13,切割方案5=2+3
r6=17,切割方案6=6(无切割）
r1=18,切割方案7=1+6或7=2+2+3
r8=22,切割方案8=2+6
r9=25,切割方案9=3+6
r10=30,切割方案10=10(无切割）

更一般地，对于rn(n≥1)，我们可以用更短的钢条的最优切割收益来描述它：

伪代码：

递归展开，计算量爆炸式增长：

两种方法：

• 带备忘录的自顶向下

如初始化为负无穷，代表未计算

• 自底向上

子问题图：

现在只是求得了最大收益，但是并没有得出切割方案！因此，需要修改dp存放的信息为切割方案，而不仅仅是最大收益。

爬楼梯

共n层楼梯，每一步只能上一层或者两层。

问有多少种不同的上法？

如3层，共3种上法：

1，1，1 ；

1，2 ；

2，1。

这里同样是一个动态规划问题，子问题为k层楼梯有多少种上法，记为f(k)。我们考虑最后一步分两种情况，即上一层或者上两层，得到f(n) = f(n- 1) + f(n - 2)。

01背包问题

给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

例如：假设你是一个小偷，背着一个可装下4磅东西的背包，你可以偷窃的物品如下：

为了让偷窃的商品价值最高，你该选择哪些商品？

首先明确，最终的背包有哪些状态？

显然，背包的重量是一个状态。

那么，这个状态可以是背包内物体的重量吗？不可以！因为它不是在数值上连续、有穷的，没法做数组下标。

换个思路考虑，我们可以把大背包拆成小背包，因此这个状态是背包的容量。

然后分析我们的选择。

我们的选择是选与不选！

首先是选不选第一个物品，再看选不选第二个物品，等等等。很明显这里有个顺序。

因此我们可以归纳出两个状态：背包容量、允许选择前几个物品。

dp[i][k]代表允许选择前i个，背包容量为j。

那么显然，当前的选择就是在前面的基础上，选不选i。

状态转移方程：

dp[i][k] = max(value[i] + dp[i-1][k-weight[i]], dp[i-1][k])

最长公共子序列/最长回文子序列

这是一个经典的问题，最长公共子序列与最长回文子序列本质上是同一个问题。注意，子序列允许不连续，而子串必须是连续的。该问题的状态为第一个字符串的前i个字符与第二个字符串的前j个字符的匹配情况，状态转移方程为：