本文总结了《王道机试指南》中动态规划(Dynamic Programming)部分的所有例题以及分析思路、状态转移方程等。有助于完整复习动态规划全部内容。为避免大量代码和题干导致失去主线,本文只写思路,代码可在题目链接内的讨论区找到。

一.基本思想

与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。
与分治法不同的是,分治法会使得有些子问题被重复计算多次。而动态规划的做法是将已解决子问题的答案保存下来,在需要子问题答案的时候便可直接获得,而不需要重复计算,节约效率。

二.经典题目

1. 递推求解问题

1.1斐波那契数列问题 (n阶楼梯上楼问题

状态转移方程:dp[n] = dp[n-1] + dp[n-2]

2. 最大连续子序列和

2.1(一维) 最大序列和问题

设置一个数组dp[ ],令dp[i]表示以A[i]作为末尾的连续序列的最大和。
状态转移方程:dp[i] = max{ A[i], dp[i-1] + A[i] }
解释:由于dp[i]是以A[i]作为结尾的连续序列最大和,因此只有两种情况:

  1. 最大和的连续序列只有一个元素,即A[i]本身。也就是dp[i] = A[i]
  2. 该最长子序列有多个元素,那么此时的dp[i] = dp[i-1] + A[i]

所以取最大值即可。

2.2(二维) 最大子矩阵问题

对于二维情况,假设原二维矩阵的最大子矩阵所在的行为 i 到 j 。

  1. 当 i = j 时,则最大子矩阵为第 i 行的最大连续子序列和。(转化为一维)
  2. 当 i != j 时,现在我们已经知道最大子矩阵的行,把从第 i 行到第 j 行的所有元素相加,得到一个只有一行的一维数组,则该一维数组的连续最大和就是最大子矩阵。(同样转化为一维)

3.最长递增子序列

3.1 拦截导弹

同样设置一个数组dp[ ] ,表以A[i]作为末尾的最长递增子序列的长度。
状态转移方程:dp[i] = max{ 1, dp[j] + 1 }。(当 j < i && A[j] < A[i] 时)
解释:由于dp[i]是以A[i]作为末尾的最长递增子序列的长度,因此只有两种情况:

  1. A[i]之前的元素都比A[i]大,即dp[i] = 1。
  2. 存在一些A[ j ]比A[ i ]小,只需找出最大的dp[j] + 1存入dp[i]

则最长递增子序列的长度即为dp中的最大值。

3.2 最大上升子序列和问题

该题目中,用dp表示的便不是长度了,而是以A[i]作为末尾的最大上升子序列和。其原理与求最长递增子序列的原理完全一致。
状态转移方程:dp[i] = max{ A[i], dp[j] + A[i] }。(当 j < i && A[j] < A[i}时)

3.3 合唱队形

这道题有点难,有时间再琢磨。

4.最长公共子序列

4.1 Coincidence(找两个字符串的最长公共子串)

这里要设置一个二维的数组 dp[][]。dp[i][j]表示以S1[i]作为末尾和以S2[j]作为末尾的最长公共子序列的长度。因此通过设置这样一个数组,最长公共子序列的长度便是数组dp[n][m]的值。
仔细说来,S1[i]和S2[j]的关系可分为两种情况:

  1. S1[i] == S2[j],即两个字符相同。此时必定存在一个最长公共子串以这个字符结尾。其他部分等价于S1中前 i - 1 个字符和S2中前 j - 1 个字符的最长公共子串。则这个子串的长度比dp[i-1][j-1]多1。即dp[i][j] = dp[i-1][j-1] + 1
  2. S1[i] != S2[j],那此时最长公共子串为S1中的前 i - 1 个字符和S2中的前 j - 1 个字符中最长公共子串长度的较大者。即dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }

状态转移方程条件
dp[ i ] [ j ] = dp[ i - 1 ] [ j - 1 ] + 1S1[ i ] == S2[ j ]
dp[ i ] [ j ] = max{ dp[ i - 1 ] [ j ], dp[ i ] [ j - 1 ] }S1[ i ] != S2[ j ]

但还要注意一下边界情况,当有一个字符串为空时,公共串长度必为0。即dp[i][0] == dp[0][j] == 0
相对于暴力枚举的O(2m+n)复杂度降至了O(mn)。

5.背包问题

5.1 0-1背包 (点菜问题

该问题描述的是,有n件物品,每件物品的重量为w[i],其价值为v[i],现在有个容量为m的背包,如何选择物品使得装入背包物品的价值最大。
如果暴力枚举所有排列组合,再从中找到最大一组,则时间复杂度为O(2n),下面以O(mn)的时间复杂度解决此问题。

首先设置一个二维数组dp[][],令dp[i][j]表示前 i 个物品装进容量为 j 的背包能获得的最大价值。通过设置这么一个二维数组,数组dp[n][m]值就是0-1背包问题的解。
只考虑第i件物品时,可将情况分为是否放入第i件物品两种:

  1. 对于容量为j的背包,如果不放入第 i 件物品,那么这个问题就转化为将前 i - 1 个物品放入容量为j的背包的问题,即dp[i][j] = dp[i-1][j]
  2. 对于容量为j的背包,如果放入第 i 件物品,那么当前背包的容量就变成了 j - w[i] ,并得到了这个物品的价值 v[i]。那么这个问题就转化成了将当前 i - 1 个物品放入容量为 j - w[i] 的背包的问题,即dp[i][j] = dp[i-1][ j-w[i] ] + v[i]

综上,可得状态转移方程:dp[i][j] = max{ dp[i-1][j], dp[i-1][ j-w[i] ] + v[i] }
转移时要注意j-w[i]的值是否为非负值,若为则代表当前容量无法放入第i件物品,不能进行转移。
再考虑一下边界情况

  • 如果装0件物品,不论背包容量多大,能够获得的价值都必为0。
  • 如果背包的容量为0,那么无法装入任何物品,能够获得的价值也必定为0。

所以,dp[i][0] = dp[0][j] = 0

6.其他问题

6.1 放苹果

链接:https://www.nowcoder.com/questionTerminal/4f0c1e21010e4d849bde5297148e81d9?f=discussion
来源:牛客网
User: 菜鸟葫芦娃

  • 设dp(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
  • 当n>m:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即if(n>m) dp(m,n) = dp(m,m)
  • 当n <= m:不同的放法可以分成两类:
    1. 有至少一个盘子空着,即相当于dp(m,n) = dp(m,n-1)
    2. 所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即dp(m,n) = dp(m-n,n)
      而总的放苹果的放法数目等于两者的和,即 dp(m,n) = dp(m,n-1) + dp(m-n,n)
#include <stdio.h>
 
int dp(int m, int n)
{
    if(n==1) return 1;
    else if(m==0) return 1;
    else if(n>m) return dp(m, m);
    else return dp(m, n-1)+dp(m-n, n);
}
 
int main()
{
    int m, n;
    while(scanf("%d %d", &m, &n)!=EOF)
    {
        printf("%d\n", dp(m, n));
    }
    return 0;
}
Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐