动态规划解题(持续更新)

记录一些动态规划问题的解题思路,会一直持续更新。

背包问题

背包问题是动态规划里面的一个大类,包括01背包,完全背包,多重背包等。N 件物品放入容量为 V 的包里,第 i 件物品占用空间 C_i,价值是 W_i。核心递推公式为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-C_i]+W_i),基本上所有问题都是由这个公式衍生而来。

能装多满

lintcode 92
在n个物品中挑选若干物品装入背包,最多能装多满?背包的大小为m,每个物品的小为A[i]
例如:有4个物品[2, 3, 5, 7],如果背包的大小为11,可以选择[2, 3, 5]装入背包,最多可以装满10的空间。

解答:

dp[i][j] 表示前 i 个物品放入 j 容量大小的包里面能装多满,对于 dp[i][j],有两种选择,第一是将 A[i] 不放入,此时,dp[i][j]=dp[i-1][j];第二是将 A[i] 放入,此时 dp[i][j]=dp[i-1][j-A[i]]+A[i]。我么当然选择两者中最大的,所以 dp[i][j]=max(dp[i-1][j], dp[i-1][j-A[i]]+A[i])

优化:

想办法优化一些空间复杂度。注意递推公式,第 i 轮更新只与上一轮即 i-1 轮的值有关,所以我们可以将空间复杂度优化到O(m)dp[j] 表示容量为 j 的背包能装多满,则 dp[j] = max(dp[j], dp[j - A[i]] + A[i])。注意此时遍历背包容量的时候要从后往前遍历,因为我们是用上一轮的第 j-A[i] 个元素更新本轮的第 j 个元素,从后往前遍历,则保证没有遍历到某元素的时候,此元素之前的元素保持不变。

能装入的最大价值

lintcode 125
题目描述:给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?
例如:对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话,最大能够装入的价值为9。

解答:

跟I问题思路一样,更新公式稍作改变:dp[i][j] = max(dp[i-1][j], dp[i-1][j-C_i]+V_i)

Coin Change

leetcode 322
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

解答:

背包问题。用dp[i]表示钱数为i时需要的硬币数,coin[j]表示硬币面值,那么显然dp[i] = min(dp[i], dp[i - coin[j]]) + 1。可见只需从前往后遍历,依次求出dp[i],最后一个即为所求。注意初始条件dp[coin[j]] = 1

Coin Change 2

leetcode 518
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

解答:

思路跟背包问题很像。
定义子问题 dp[i][j] : 用前 i 种硬币组成金额 j 的总组合数;
最终目标:dp[n][amount]
dp[i][j] 时:

  1. 不用第 i 种硬币。

    • 用不了:j < coins[i];
    • 能用但不用。 两种情况都只用前 i-1 种硬币去组成 j, 此时共有 dp[i-1][j] 种组合;
  2. 用第 i 种硬币, 此时因为硬币无限,所以它的前一个状态仍能用 i 种硬币,即此时共有 dp[i][j-coins[i]] 种组合。

因此总的组合数是两种情况的和:dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]

优化:

优化空间,dp[j] 表示用前 i 种银币组成金额 j 的总组合数,在迭代时 dp[j] = dp[j] + dp[j - coins[i]]

正则表达式匹配

leetcode 10
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 .* 的正则表达式匹配。
. 匹配任意单个字符。
* 匹配零个或多个前面的元素。

解答

dp[i][j]表示s的i长度跟p的j长度是否使用匹配。则有以下情况。

  1. dp[0][0]: 表示当s和p都为空,此时肯定是匹配的,dp[0][0] = 1;

  2. 当s为空"",p为'a*'时,唯一可能match的情况是p匹配为空串,取决于dp[0][j-2]。如:

    1
    2
    s: " "     
    p: "a*b*c*"
  3. s[i-1] == p[j-1] || p[j-1] == '.' : dp[i][j] = dp[i-1][j-1]

  4. p[j-1] == '*',分下面两种情况讨论:

    • 如果p[j-2] != s[i-1] && p[j-2] != '.': 只能把它匹配成一个空串,即0个字符,dp[i][j] = dp[i][j-2]
    • 否则,可能匹配0个字符,1个字符,多个字符,即dp[i][j] = (dp[i][j-2] || dp[i][j-1] || dp[i-1][j])

代码中注意动态规划的初始赋值。

最长有效括号

leetcode 32
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解法一:动态规划
dp[i]表示一i索引为结尾的最大匹配长度,

  1. s[i](时:dp[i] = 0
  2. s[i] == ')' && s[i-1] == '('dp[i] = dp[i - 2] + 2
  3. s[i] == ')' && s[i-1] == ')' && s[i- dp[i-1] - 1] == '('dp[i] = dp[i - dp[i-1] - 2] + dp[i-1] + 2

解答二:栈
维持一个(索引的栈,当遇到)时弹出。同时维护一个最左端可以匹配的索引,初始为left = -1。当遇到),做以下判断:

  1. 栈为空时,就left = i,继续遍历,否则执行2;
  2. 栈不为空时,先pop一个index出来,然后判断栈是否为空。栈为空时,nMax = max(nMax, i - nLeft);栈不空空时,nMax = max(nMax, i - stack.top())

地下城游戏

leetcode 174
最初勇士位于左上角,要走到右下角,每次只能向右或向下。格子中的数字表示在这里会补血或者失血多少。正补负失。当血量小于等于0时勇士立即死去,试问确保骑士能够活着到达右下角所需的最低初始血量。
例如下表,最佳路径 右 -> 右 -> 下 -> 下,血量至少为7。

-2 -3 3
-5 -10 1
10 30 -5

解答:

dp[i][j]表示勇士进入(i,j)时至少需要的点数。

假设一种情况:勇士位于一个比较中间的位置(i, j)。先来决定从右走还是从下走。如果从右边走,进入右边时点数至少为8才能最终到达终点;如果从下边走至少需要3点才能最终到达终点。那毫无疑问,我们肯定选择从下面走。而在当前位置,需要失血6点,所以进入当前位置时,血量至少为3-(-6)=9

从这个过程我们分析可知,当前位置进入时的血量取决于它后面的位置需要的血量和当前位置补血失血情况,所以需要从后往前计算。具体就是dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - current[i][j],需要注意的是,如果此时计算出来的dp[i][j] <= 0,那就要置为1。

打家劫舍

leetcode 198
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
输入: [1,2,3,1]
输出: 4

解答:

dp[i]表示小偷光顾第i个房屋后总共获取的最大金额。显然,第i个房间可以进行两种选择,偷或者不偷。不偷:dp[i] = dp[i-1];偷:dp[i] = dp[i-2] + nums[i]。当然我们选择金额最大的。则:dp[i] = max(dp[i-1], dp[i-2] + nums[i])

优化:

观察递推公式,发现下一个值只和上一个、上两个值相关,所以可以将空间优化到O(1)

Paint House I

lintcode 515
这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小。
费用通过一个 nx3 的矩阵给出,比如cost[0][0]表示房屋0染红色的费用,cost[1][2]表示房屋1染绿色的费用。
输入:costs = [[14,2,11],[11,14,5],[14,3,10]]
输出:10

解答:

dp[i][j]表示第i个房屋使用第j中颜色时所花费的最少费用,显然dp[i][j] = costs[i][j] + min(dp[i][n != j])

Paint House II

lintcode 516
这里有n个房子在一列直线上,现在我们需要给房屋染色,共有k种颜色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小。
费用通过一个nxk 的矩阵给出,比如cost[0][0]表示房屋0染颜色0的费用,cost[1][2]表示房屋1染颜色2的费用。
输入:costs = [[14,2,11],[11,14,5],[14,3,10]]
输出:10
限制:用O(nk)的时间复杂度来解题

解答:

这道题是之前那道 Paint House I 的拓展,那道题只让用红绿蓝三种颜色来粉刷房子,而这道题让我们用k种颜色,这道题不能用之前那题的解法,会TLE。这题的解法的思路还是用DP,但是在找不同颜色的最小值不是遍历所有不同颜色,而是用min1min2来记录之前房子的最小和第二小的花费的颜色,如果当前房子颜色和min1相同,那么我们用min2对应的值计算,反之我们用min1对应的值,这种解法实际上也包含了求次小值的方法,感觉也是一种很棒的解题思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty() || costs[0].empty()) return 0;
vector<vector<int>> dp = costs;
int min1 = -1,
int min2 = -1;
for (int i = 0; i < dp.size(); ++i)
{
int last1 = min1,
int last2 = min2;
min1 = -1;
min2 = -1;
for (int j = 0; j < dp[i].size(); ++j)
{
if (j != last1)
{
dp[i][j] += last1 < 0 ? 0 : dp[i - 1][last1];
}
else
{
dp[i][j] += last2 < 0 ? 0 : dp[i - 1][last2];
}
if (min1 < 0 || dp[i][j] < dp[i][min1])
{
min2 = min1; min1 = j;
}
else if (min2 < 0 || dp[i][j] < dp[i][min2])
{
min2 = j;
}
}
}
return dp.back()[min1];
}
};
持续技术分享,您的支持将鼓励我继续创作!