动态规划

首要内容

• 动态规划的基本性质和过程
• 最大子数组问题
• 0-1背包问题
• 旅行商问题
• 状况紧缩动态规划

引例：斐波那契数列

从图片中不难看出，递归算法自顶向下的核算思路中，存在很多重复核算，当n的取值过大时，递归需求占据很多的时刻和空间，需求优化。

解决方法 选用自底向上的核算方法，从第一个元素开端核算，从而消除重复核算。

基本性质

1. 和分治类似：动态规划也是将原问题分解为子问题求解。
2. 和分治不同：不是通过递归的方法，而是自底向上的求解问题。

机器人行走

还记得吗？这个标题咱们在分治一章中讨论过，只能向右或向上行走，则到达结尾的途径条数path(i,j) = path(i-1,j) + path(i,j-1).

• 分治需求核算多少次？55次。

• 动态规划需求的核算次数：12次。

  

动态规划适用的场景：

• 子问题并不独立，即子问题是或许重复的。
• 首要用于优化问题（求最优解），且问题具有最优子结构性质。

什么是最优子结构性质？

最优子结构性质指原问题的最优解必定包括了子问题的最优解。例：最短途径问题具有最优子结构性质，最长途径问题则不具有。

基本过程

1. 界说子问题，并分析最优解的结构性质：分治通常是将原问题对半分，而动态规划是将n规划的问题分解成n-1规划的问题。
2. 找出最优解对应的最优值，并递归地界说最优值。
3. 以自底向上的方法核算出最优值
4. 依据核算最优值得到的信息，结构最优解。

最大子数组问题

0-1背包问题

0-1背包问题：给定n种物品和一个背包，物品i的分量是wi，其价值为vi，背包的容量为C（总承重为C），问应如何挑选装入背包的物品，使得装入背包中的物品的总价值V最大化。

分析0-1背包问题的最优解的结构特征

• 一种情况是第n个物品不包括在最优解里：设x* = (x1,x2,…,xn-1,xn)，则(x1,x2,…,xn-1)必为n-1个物品（剔除第n个物品），且背包容量为C情况下的最优解。
• 第二种情况是第n个物品包括在最优解里边：则(x1,x2,…,xn-1)必为n-1个物品，背包容量为C-wn情况下的最优解。

找出0-1背包问题最优解对应的最优值，并递归地界说最优值

在n个物品里，背包容量为C情况下的总价值，咱们用m(n,C)表明最优值。

自底向上地求解最优值

依据m值矩阵得出最优解

所以最优解为{a,b,c}，最优值为16。

0-1背包最优解
for i=1 to n do
  if m(i,c)==m(i-1,c) then
    x[i]=0
  else
    x[i]=1
    c=c-w[i]
  end if
end for
return x

算法复杂度分析： 从m(i,j)的递归式简单看出，算法需求O(nc)的核算时刻。当背包容量C很大时，算法需求的核算时刻较多。例如，当C>2^n时，算法需求(n2^n)核算时刻。

旅行商问题

旅行商问题最优解的结构特征

• 最优子结构性质：假定途径c1c2…cn-1cnc1是城市{c1,c2,…,cn-1,cn}的最短环路，取这个途径的任何一个子途径，如c1c2…ci必然是城市{c1,c2,…,ci}中从c1到ci通过其他城市一次且仅一次的最短途径。
• 旅行商问题的子问题是明显堆叠的：如下两个途径c1c2c3c4…cn和c1c3c2c4…cn都具有相同的子途径c4…cn-1cn。

旅行商问题最优解对应的最优值，并递归地界说最优值

自底向上求解最优值

在此算法中，因TSP(c1,C,ci)中的c1可忽略，咱们用一个二维数组TP[C][ci]存储TSP(c1,C,ci)的值，算法总复杂度为O(n^2 * 2^n)

结构最优解

while循环（语句4-18）依次往最短途径添加城市，每次添加实际上便是找出下一层哪一个TSP和当时城市c^形成了最短回路。

最长公共子序列

最长公共子序列的结构

子问题的递归结构

自底向上核算c[i][j]

核算最优值

由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地核算最优值能进步算法的功率。

结构最长子序列

状况紧缩动态规划

• 调集状况紧缩：用二进制表明调集，之后用整型表明二进制，如旅行商问题中的TP数组。
• 空间状况紧缩：自底向上的方法求解最优值的过程中，紧缩最优值的存储空间。

调集状况紧缩

整数的一些基本位操作：

• 判断第i比特是否为0：D&(L<<i)==0，若真，则为0，如假，则为1，其中L<<i表明将L左移i位；
• 将第i比特设置为1：D|(L<<i)；
• 将第i比特设置为0：D&(~(L<<i)；
• 将第i比特取反：D⊕(L<<i)；
• 取出第i比特:D&(L<<i)；

需求判断一下：j所代表的城市调集C是否包括了i所代表的城市，假如不包括，就无需做任何处理，如包括，则依次比较j调集所有下一层的TP值。

空间状况紧缩