动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
重叠子问题
子问题可以被一个递归算法多次的重复访问。区别分治算法中的子问题，那个子问题是独立的
举个例子：求斐波那契数列时fib(8)=fib(7)+fib(6)，其中fib(8)的最优解就包含了子问题fib(7)的最优解和子问题fib(6)的最优解，反过来讲只要我们求解出子问题的最优解，那么就可以构造出问题的最优解，这也就是为什么最优子结构是求解动态规划的必要条件。fib(7)和fib(6)中有相同的子问题fib(5)，这就是子问题重叠。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化（en:memoization）存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用.
动态规划的思路
通过寻找最优子结构同时记录最优结构，从而将复杂的大问题转化为小问题的求解过程，最近针对于动态规划做了些练习，找到些解题的思路和感觉，下面针对于几个问题来逐步的分析下动态规划。
案例分析
背包问题（0-1背包）
问题描述
给定背包容量W，n个物品及各个物品的价值和重量，问如何选择使背包能装下物品的价值最大？
寻找子问题
当包能容纳w的时候，有i种物品可以选择的情况下，最优解是dp[i,j]。
定义数据结构
-背包容量W
-物品个数n
-各个物品价值和重量分别为v[n], w[n]
定义最优解
-假设选择物品前，已经给所有物品编号，i是可选物品的最小编号
-j是背包剩余容量
-综合理解dp(i,j)：在背包剩余容量为j的前提下，可选物品编号为i,i+1,⋯,n的时候，背包的最大价值。其中i∈Z,i∈[0∼n],j∈[0∼C]。如何想到这样定义最优值的？我的想法是，最优值是一个“时间剪影”，考虑“选物品，装背包”的过程，在某一个时刻停下，描述此刻的状态(值)。具体的定义则是过程下一步，如下：
-(动态规划数组)dp[n][W]，dp[i][j]表示当背包容量达到j时，前i个物品所具有的最佳价值组和
状态转移方程
对第i个物品的判断，有两种可能性：
该物品重量大于当前背包容量，则dp[i][j] = dp[i-1][j]
该物品重量小于当前背包容量时，并不是无脑加入，而需要判断加入该物品后背包容量剩余j-w[j]时的价值是否会比不加入物品i大
那么可写出如下状态转移方程：
image.png
实列
image.png
做题思路
-分析数据结构
-定义最优解
-建立状态转移方程
-建立存储表格https://blog.csdn.net/qq_38410730/article/details/81667885
算法思想
for w = 0 to W
dp[0,w] = 0
for i =1 to n
for w = 1 to W
if (wi > w)
dp[i,w] = dp[i-1,w]
else
dp[i,w] = max {dp[i-1,w], vi + dp[i-1,w-wi]}
return dp[n,w]
代码实现
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 105;
int v[maxn], w[maxn], dp[maxn];
int main()
{
int n; cin >> n;
int W; cin >> W;
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
memset(dp, 0, sizeof(dp));
for(int i=1; i<=n; i++)
cin >> w[i] >> v[i];
for(int i=1; i<=n; i++){
int ww = W;
for(; ww>=w[i]; ww--){ //注意是从大到小的顺序
dp[ww] = max(dp[ww], dp[ww-w[i]]+v[i]); //递推公式
}
}
cout << dp[W];
return 0;
}
参考：https://www.jianshu.com/p/f36344f7aa39
硬币找零问题
参考https://juejin.im/post/5b0a8e0f51882538b2592963
问题描述
给定4种面额的硬币1分，2分，5分，6分，如果要找11分的零钱，怎么做才能使得找的硬币数量总和最少。
寻找子问题
当零钱总额为j时，提供的面值为i的时候，它的最优解为m[i,j]。
分析
最少硬币找零问题，是为了求硬币的组合，所以一个大前提是硬币无限量供应。我们建立如下表格来分析问题：
image.png
其中每列用j表示零钱总额，每行i表示硬币面额。T[i][j]表示硬币个数，它是我们即将填入表格的数字。
在填写表格之前，我们需要先明确几个规则：
当填写第i行时，使用的硬币面额仅能是i以及小于i的面额。举个例子，比如我填写第0行，i=0，那么这一样只能使用面额为1分的硬币。当我填写第2行，i=2，那么可以使用1分，2分，5分三种面额的硬币。
当填写第j列时，表示当前需要使用硬币凑出的总额。比如j=6，表示需要使用硬币组合出总额为6分的情况。
定义最优解
m[i,j]则表示的是当可以提供i种面额的硬币时，要凑出总额所需要的最少的硬币数。
v[i]表示当前i硬币的面值。
j表示零钱的总额
-
i = 0
当我们只能使用面额为1分的硬币时，根据上面的规则，那么很显然，总额为几分，就需要几个硬币。即T[i][j] = j。
image.png
- i = 1
当我们有1分和2分两种面额时，那么组合方式就相对多了点。
i=1 j = 1：总额为1时，只能使用1分的面额。即填1。
i=1 j = 2：总额为2时，可以使用2个1分的，也可以使用1个2分的。因为我们要求最少硬币，所以使用1个2分的。表格所表达的意思是硬币的数量，所以这里也填1。
i=1 j = 3：总额为3时，可以使用3个1分的，也可以使用1个1分加1个2分。因此这里应该填2。
i=1 j = 4：总额为4时，可以使用4个1分的，可以使用2个1分加1个2分，也可以使用2个2分。其中硬币最少的情况应该是2个2分。因此这里填2。
i=1 j = 5：总额为5时，组合就更多了，但是聪明的你应该能想到使用2个2分加1个1分，可以实现最少硬币的需求。因此这里填3。
image.png
3.接着写几个找规律。
发现：当v[i]<j；m[i,j] = m[i-1,j]
当v[i]>j; m[i,j] = m[i-1,j-v[i]n] + n) 其中n为j/v(i)的商，j-v[i]n为j/v(i)的余数。 或者当v[i]>j; m[i,j] = min(m[i-1,j],m[i,j-v[i]] +1)
算法实现
if(i == 0){
T[i][j] = j/coins[i]; //硬币找零一定要有个 最小面额1，否则会无解
}else{
if(j >= coins[i]){
T[i][j] = min(T[i-1][j],1+T[i][j-coins[i]])
}else{
T[i][j] = T[i-1][j];
}
}
最长上身子序列问题（LIS）
参考: https://www.jianshu.com/p/6fc54cec4b4c
问题描述
给定n个数字的序列，如11，3，6，9，13，14，18，12，15，2，16，20，8，19，问最长的上升序列长度是多少。
上升序列，分为严格单调递增序列和单调不减序列。前者需满足序列L中，i<j，L[i]<L[j]，而后者可取等号。例如，上述序列中存在一个递增序列{3，8，19}，显然不是最长的上升子序列。
寻找子问题
“求以ak（k=1, 2, 3…N）为终点的最长上升子序列的长度” 一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。
分析
因为递增的判断是在原序列末尾元素基础上进行比较的，是动态规划典例。递推关系如下：
对于每个元素s[i]，向前找所有小于s[i]的元素。
状态转移方程
-若存在s[j]<s[i]（j<i），则dp[i] = max{ max{dp[j]} + 1,max{dp[k]} },k为小于i的整数
-若不存在s[j]<s[i]（j<i）,则s[i]自身构成一个子序列，dp[i] = max{dp[k]}，k为小于i的整数
image.png
实例求解
dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=4, dp[6]=5, dp[7]=6, dp[8]=6, dp[9]=6, dp[10]=6, dp[11]=7, dp[12]=8, dp[13]=8, dp[14]=8
算法
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
int s[maxn], dp[maxn];
int main()
{
int n; cin >> n;
for(int i=0;i<n;i++) cin >> s[i];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int i;
for(i=1;i<n;i++){
int tem_max=0;
for(int j=0;j<i;j++){
if(s[j]<s[i]) tem_max = max(tem_max, dp[j]);
}
dp[i] = tem_max+1;
}
cout << dp[n-1];
return 0;
}
上面代码的复杂度为O(n^n)，每次考虑一个元素都需要和它之前的数依次比较一遍，比较笨。我们思考是否可以用一个数组保存当前最佳的最长子序列，这样每次新加入一个数，只需将其与数组最后一个元素比较即可。
这会引入一个问题，保存的最长上升子序列的数组是动态变化的，并且为贪心使尽可能更多的元素加入，需要不断修改数组元素为不改变大小关系的最小值。
例如，已有当前的最长子序列{3，6，9，13，14，18}，当遇到12时，比较18>12，那么寻找数组中第一个大于12的元素将其替换。处理完12得到的子序列是{3，6，9，12，14，18}，长度不变，需要特别注意的是，此序列不能代表真实的最长上升子序列，只是为求解序列长度提供的一种量化方法。
将复杂度降到O(nlgn)，代码如下
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
int s[maxn], lis[maxn];
int bi_search(int A[], int right, int left, int num){ //二分查找递增数列a[n]中第一个大于num的元素下标，并返回
int mid;
while(right<left){
mid = (right+left)/2;
if(num<=A[mid]) left = mid;
else right = mid+1;
}
return left;
}
int main()
{
int n; cin >> n;
int maxl;
for(int i=0;i<n;i++) cin >> s[i];
memset(lis, 0, sizeof(lis));
lis[0] = s[0]; maxl = 1; //maxl表示lis数组元素个数，即最长上升子序列长度
for(int i=1;i<n;i++){
if(lis[maxl-1]<s[i])
lis[maxl++] = s[i];
else if(lis[maxl-1]==s[i]) continue;
else{
int p = bi_search(lis, 0, maxl-1, s[i]);
lis[p] = s[i];
}
}
cout << maxl;
return 0;
}
最长公共子序列问题（LCS）
参考：
https://www.jianshu.com/p/ccab8ef5f979 https://blog.csdn.net/hrn1216/article/details/51534607
问题描述
子序列是指，从序列中选出一些子元素，需满足其前后关系与在原序列中相同；公共是指该序列同时是两个序列的子序列。如两个序列{4，2，1 ，6，5，8，13，18，9，5}和 {3，2，1，9，10，6，5，9}，{2，1}和{1，6，5}都是它们的公共子序列，显然，这不是最长的。那么如何求解两个序列的最长公共子序列（LCS）？
分析
设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：
如果am=bn，则zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列；
如果am!=bn，则若zk!=am，蕴涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；
如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一个最长公共子序列。
image.png
（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），并结合上图来说：
假如S1的最后一个元素 与 S2的最后一个元素相等，那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。
假如S1的最后一个元素 与 S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的LCS就等于 ： {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。
状态转移方程
image.png
序列增长过程
image.png
编辑距离问题
问题描述
给定 2 个字符串 a, b. 编辑距离是将 a 转换为 b 的最少操作次数，操作只允许如下 3 种：
插入一个字符，例如：fj -> fxj
删除一个字符，例如：fxj -> fj
替换一个字符，例如：jxj -> fyj
状态转移方程
参考：https://www.jianshu.com/p/6afaf20bb831
image.png
旅行商问题
问题描述
TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
假设现在有四个城市，0,1,2,3，他们之间的代价如图一，可以存成二维表的形式
image.png
现在要从城市0出发，最后又回到0，期间1，2，3都必须并且只能经过一次，使代价最小。
动态规划可行性
设s, s1, s2, …, sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, …, sp, s一定构成一条从s1到s的最短路径，所以TSP问题是构成最优子结构性质的，用动态规划来求解也是合理的。
状态转移方程的推导
假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。
推导：(分情况来讨论)
①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的 城市3->城市0(0为起点城市)。此时d(i, V’)=Cis(就是 城市i 到 城市s 的距离)、
②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个，并求出最优解。
d(i, V’)=min{Cik + d(k, V’-{k})}
注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。
综上所述，TSP问题的动态规划方程就出来了：
image.png
实例
现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)
image.png
①我们要求的最终结果是d(0,{1,2,3}),它表示，从城市0开始，经过{1,2,3}之中的城市并且只有一次，求出最短路径.
②d(0,{1,2,3})是不能一下子求出来的，那么他的值是怎么得出的呢？看上图的第二层，第二层表明了d(0,{1,2,3})所需依赖的值。那么得出：
d(0,{1,2,3})=min {
C01+d(1,{2,3})
C02+d{2,{1,3}}
C03+d{3,{1,2}}
}
③d(1,{2,3})，d(2,{1,3})，d(3,{1,2})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3})
d(1,{2,3})=min{
C12+d(2,{3})
C13+d(3,{2})
}
d(2,{1,3})，d(3,{1,2})同样需要这么求。
④按照上面的思路，只有最后一层的，当当V’为空集时，Cis的值才可以求，它的值是直接从下面这张表求出来的。
image.png
二维表
将d(i, V’)转换成二维表，d[i][j]
image.png
在程序中模拟填表的过程，主要要考虑到j这个参数的表示，它要代表一个集合，可以用二维数组来表示。
原文链接：https://blog.csdn.net/joekwok/article/details/4749713
有向无环图求最长路径
问题描述
给定一个带权有向无环图及源点S,在图中找出从S出发到图中其它所有顶点的最长距离。
对于一般的图，求最长路径并不向最短路径那样容易，因为最长路径并没有最优子结构的属性。实际上求最长路径属于NP-Hard问题。然而，对于有向无环图，最长路径问题有线性时间的解。思路与通过使用拓扑排序在线性时间求最短路径[1]一样。
首先初始化到所有顶点的距离为负无穷大，到源点的距离为0，然后找出拓扑序。图的拓扑排序代表一个图的线性顺序。（图b是图a的一个线性表示）。当找到拓扑序后，逐个处理拓扑序中的所有顶点。对于每个被处理的顶点，通过使用当前顶点来更新到它的邻接点的距离。
过程
-图(b)中，到点s的距离初始化为0,到其它点的距离初始化为负无穷大，而图(b)中的边表示图(a)中边的权值。
-图(c)中，求得从s到r的距离为负无穷。
-图(d)中，求得s到t的最长距离为2,到x的最长距离为6。
-图(e)至图(h)依次求得可达点间的最长距离。
参考：https://blog.csdn.net/Revivedsun/article/details/51286777
网友评论