11-dynamic-programming

发表于 更新于 分类于 阅读次数： 本文字数： 4.7k 阅读时长 ≈ 4 分钟

动态规划

《算法笔记》第11章，动态规划

动态规划基本介绍

动态规划（Dynamic Programming, DP）是很精妙的算法，没有固定的写法。基本思想是把一个复杂问题拆分为几个不同的子问题，通过综合子问题的最优解来获得复杂问题的最优解。理解动态规划有以下几点需要注意：

  • 应用动态规划的前提是复杂问题的最优解可以通过其子问题的最优解来获得，如果一个问题满足这样的性质，就称该问题具有最优子结构（Optimal Substructure）。
  • 动态规划与分治法的区别是：分治法划分子问题没有重叠，一个子问题不会再重复的出现；动态规划划分出的子问题会重复的出现，因此动态规划通常会记录子问题的解，当再次遇到子问题时直接给出解。另外，分治法不一定是在解决最优问题，动态规划则总是在找最优解。
  • 动态规划与贪心法的区别是：贪心算法会依赖于当前状态，在多个子问题中直接选择当前最优的子问题，而不再考虑其它子问题，因此贪心算法能否真的找到最优解还依赖于分析证明；动态规划会考虑所有子问题，在后续的步骤中可能会重新考虑之前的子问题，不断综合子问题的最优解，保证最后能够找到最优结果。

接下来考虑几个经典的动态规划算法

最大连续子序列和

给定一个数字序列A，求最大的连续数字序列的和。

思路：对于i位的数字，规定以i位数字结尾的最大连续序列和为dp[i]，那么dp[i]=max(A[i], dp[i-1]+A[i])，最大的子序列和就是所有dp[]的最大值。核心就是这个状态转移方程，可以看到当前状态仅仅依赖于已有的状态，一旦当前状态确定后，不会在后续的步骤中改变。动态规划的核心难点就是这一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
  int dp[n];
  dp[0] = A[0]; // 初始化首位
  for(int i = 1; i < n; ++i) {
		dp[i] = max(dp[i-1]+A[i], A[i]);
  }
  // 检查最大值
  int MAX = dp[0];
  for(int i = 1; i < n; ++i) {
    if(dp[i]>MAX) {
      MAX = dp[i];
    }
  }
  printf("%d\n", MAX);
}

最长不下降子序列（LIS）

给定一个序列，求最长的可不连续、非递降子序列（Longest Increasing Sequence, LIS）。

思路：对于A[i]，遍历所有的A[0]-A[i-1]，如果存在一个元素A[k]比A[i]小或者相等，那么计算下dp[k]+1，选择最大值保存为dp[i]。同样，无论dp[i]之后出现什么新元素，不会改变dp[i]，dp[i]也只依赖于之前已有的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main() {
  int dp[n];
  dp[0] = 1;
  for(int i = 1; i < n; ++i) {
    dp[i] = 1;
    // 遍历以前所有的元素，保存LIS值
    for(int j = 0; j < i; ++j) {
      if(A[j]<=A[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  // 检查最大不下降序列
  int MAX = dp[0];
  for(int i = 0; i < n; ++i) {
		if(MAX<dp[i]) MAX = dp[i];
  }
  printf("%d\n", MAX);
}

最长公共子序列（LCS）

给定两个序列A和B，求最长的公共可不连续子序列（Longest Common Seqence, LCS）

思路：对于A[i]和B[j]，如果A[i]==B[j]，那么LCS+1；如果A[i]!=B[j]，那么LCS=max(dp[i][j-1], dp[i-1][j])。初始化的边界是dp[0][j]=0和dp[i][0]=0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
  int m,n; // m是序列A的长度，n是序列B的长度
  int dp[m+1][n+1];
  // 初始化
  for(int i=0;i<m;++i) {
    dp[i][0] = 0;
  }
  for(int j=0;j<n;++j) {
    dp[0][j] = 0;
  }
  
  // 从下标1开始，避免i-1小于0
  for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
      if(A[i]==B[j]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      }
      else {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  printf("%d\n", dp[m][n]); // 此时，dp[m][n]就是最大公共子序列
}

最长回文子串

回文是指从左向右和从右到左读的结果都一样的序列。检验回文只需要两个指针从两端分别检查是否元素相等，直至相遇即可。

给定序列A，要求输出最长的回文串。

思路：如果dp[i][j]中，如果A[i]==A[j]，并且dp[i+1][j-1]是回文串，那么dp[i][j]也是回文串；如果A[i]!=A[j]，那么dp[i][j]不是回文串。这里在实现的时候，问题在于不能直接按照i，j的循环遍历，因为这样会造成dp[i+1]在dp[i]之后出现。因此需要想办法先计算好dp[i+1][j-1]，考虑到长度问题，使用长度来作为循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
  int dp[n][n]; // n是序列A长度，dp[i][j]=1表示序列i->j是回文子串
  int ans = 1; // 初始化的最大回文子串长度
  for(int i=0; i<n; ++i) {
    dp[i][i] = 1;
  }
  // 子问题的长度从2-n
  for(int L=2; L<=n; L++) {
    for(int i=0; i + L - 1<n; i++) {
      int j = i + L - 1;
      if(A[i] == A[j] && dp[i+1][j-1] == 1) {
        dp[i][j] = 1;
        ans = L;
      }
    }
  }
  printf("%d\n", ans);
}

DAG最长路径

这里使用DP的思想解决有向无环图DAG的最长/最短路径问题，思想实际比dijkstra等算法更加简单易理解。

求一个DAG中的最长路径，不规定起点和终点

思想：令dp[i]表示从顶点i出发能够到达的最长路径，那么dp[i]=max{dp[j]+G[i][j]}，顶点j是顶点i的后继顶点。很明显这是一个逆拓扑排序的顺序，使用递归的方法可以简单实现。最后只需要在所有的dp[i]中搜索最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int choice[maxn]; // 记录选择的后继结点，初始化为-1
int DP(int i) {
  // dp初始化全为0
  if(dp[i]>0)
    return 0;
  for(int j=0;j<n;++j) {
		if(G[i][j]!=INF && dp[i]<DP(j)+G[i][j]) {
      dp[i] = dp[j]+G[i][j]; // 更新
      choice[i] = j;
    }
  }
  return dp[i];
}

void printPath(int i) {
  while(choice[i]!=-1) {
    printf("%d ", i);
    i = choice[i];
  }
}

求一个DAG中，固定重点T的最长路径

思想：令dp[i]表示从顶点i出发能够到达终点T的最长路径，那么dp[i]=max{dp[j]+G[i][j]}，顶点j是顶点i的后继顶点。和上面的问题最大区别是如何体现能够到达终点T？前面使用dp[i]==0代表已经到了终点，如果还是使用0表示到达终点T，这会导致无法区分出不能到达T的顶点，那些无法到达终点T的路径也被考虑，最后输出错误结果。因此，考虑让dp[i]初始化为-INF，这样不能到达T的路径都会取到很小的值，从而被排除。

1
2
3
4
5
6
7
8
9
10
11
12
13
int DP(int i) {
  // dp初始化全为-INF
  if(vis[i]==true)
    return dp[i];
  vis[i] = true;
  for(int j=0; j<n; ++j) {
		if(G[i][j]!=INF && dp[i]<DP(j)+G[i][j]) {
      dp[i] = dp[j]+G[i][j]; // 更新
      choice[i] = j;
    }
  }
  return dp[i];
}

背包问题

01背包

n种物品，价值和重量分别为c[i]和w[i]，每种物品只有1件，要求总背包承重是V的情况下，总价值最大。

思路：第i种物品是否放入背包容积v的最大值由前i-1种物品完全决定。dp[i][v]=max(dp[i-1][v], dp[i-1][v-w[i]])。为了减小二维数组的开销，可以使用滚动数组的方法，只使用一个动态改变值的一维数组来实现。注意到计算i的时候，i-1是固定值，完全可以把i-1看做是上一轮数组的结果，同样还是两层循环，i:1->n, v:V->w[i]。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
  int dp[V+1];
  // 初始化
  for(int v=0;v<V+1;++v) {
    dp[v] = 0;
  }
  for(int i=1; i<=n; ++i) {
    // 这里必须是逆序排列，第i轮计算要用到第i-1轮的新结果
    for(int v=V; v>=w[i]; --v) {
      dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
    }
  }
  // 寻找最大值
  int max = 0;
  for(int v=0;v<V+1;++v) {
    // pass
  }
}

完全背包

n种物品，价值和重量分别为c[i]和w[i]，每种物品有任意件，要求总背包承重是V的情况下，总价值最大。

思路：第i种物品是否放入背包容积v的最大值由前i-1种物品完全决定。dp[i][v]=max(dp[i-1][v], dp[i][v-w[i]])。和01背包的区别就是放入i种物品后，还可以继续考虑放入第i种物品。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
  int dp[V+1];
  // 初始化
  for(int v=0;v<V+1;++v) {
    dp[v] = 0;
  }
  for(int i=1; i<=n; ++i) {
    // 这里必须是正序排列，第i轮计算要用到第i轮的新结果
    for(int v=w[i]; v<=V; --v) {
      dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
    }
  }
}