Garden | Dynamic Programming

动态规划

背包问题

Coin Change

https://leetcode.com/problems/coin-change

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2：

输入：coins = [2], amount = 3 输出：-1

思路分析

硬币相当于我们的物品，每种硬币可以选择「无限次」，我们应该很自然的想到「完全背包」。

如果不能，那么从现在开始就要培养这样的习惯：

当看到题目是给定一些「物品」，让我们从中进行选择，以达到「最大价值」或者「特定价值」时，我们应该联想到「背包问题」。

这本质上其实是一个组合问题：被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

状态定义：

dp[i][j] 表示使用前 i 中硬币凑成 amount 所需要的最小硬币数

状态转移：

dp[i][j] =min(dp[i-1][j], dp[i-1][j-k*coin[i]]+k)

初始化：

dp[0][0] = 0
dp[0][j] = INT_MAX

参考完全背包问题的一维空间优化，状态转移为：

dp[j] = min(dp[j], dp[j-coin[i]]+1)

注意事项：

因为都是初始化为最大值，所以如果 dp[j-coin[i] == INT_MAX 时避免加1，否则会溢出

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();

        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = coins[i-1]; j <= amount; j++) {
                if (dp[j-coins[i-1]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j-coins[i-1]] + 1);
            }
        }

        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

类似题目：Perfect Squares

Coin Change 2

题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。示例 1：

输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2：

输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。

思路分析

状态定义：

dp[i][j] 表示考虑前 i 件物品，凑成总和为 j 的方案数量

初始化条件：

dp[0][x] = 0, x > 1
dp[0][0] = 1

状态转移：

对于第 i 个硬币，不使用该硬币 dp[i][j] = dp[i-1][j]
对于第 i 个硬币，可以使用多次（容量允许的条件下），dp[i][j] = dp[i-1][j-v[i]] + dp[i-1][j-2*v[i]]+...+dp[i-1][j-k*v[i]]

状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]] + dp[i-1][j-2*v[i]]+...+dp[i-1][j-k*v[i]]

参照完全背包问题的换元优化方式：

dp[i][j-v[i]] = dp[i-1][j-v[i]] + dp[i-1][j-2*v[i]] + dp[i-1][j-3*v[i]]+...+dp[i-1][j-k*v[i]]

所以：

dp[i][j] = dp[i-1][j] + dp[i][j-v[i]]

简化为一维：

dp[j] = dp[j] + dp[j-v[i]]
初始化条件：dp[0] = 1，dp[x] = 0

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[] f = new int[cnt + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = val; j <= cnt; j++) {
                f[j] = f[j] + f[j - val];
            }
        }
        return f[cnt];
    }
}

Ones and Zeroes

问题总结

0/1 背包问题

参考 https://www.acwing.com/problem/content/description/2/

问题描述

描述：有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路分析

0-1 背包问题是众多背包问题中最简单的，其特点是物品不能重复放入。

定义状态函数：

dp[i][j] 表示前 i 件物品放入一个容量为 j 的背包可以获得的最大价值。

状态转移方程为：

dp[i][j] = max(dp[i - 1][j], w[i] + dp[i - 1][j - v[i])

即对于第 i 件物品，我们有两种决策方案：

不选择第 i 件物品，则最大价值等于 dp[i - 1][j] ，全部容量留给前 i - 1 件物品
选择第 i 件物品，则最大价值等于 w[i] + dp[i - 1][j - v[i]] ，其中 w[i] 代表当前物品的价值，这样就用掉了 v[i] 的体积，留给前 i - 1 件物品的容量就剩下 j - v[i]，所以总的价值等于 w[i] + dp[i - 1][j - v[i]]

初始化：

设置边界 dp[0][j] 和 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


#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int dp[N][N], v[N], w[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ ) // 枚举每个物品
        for(int j = 0; j <= m; j ++ ){
            dp[i][j] = dp[i - 1][j]; // 不选这个物品
            if(j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); // 选这个物品
        }
    cout << dp[n][m] << endl;
}

一维空间优化

在 01 背包中，最重要的是「一维空间优化」解法。

根据状态转移方程 dp[i][j] = max(dp[i - 1][j], w[i] + dp[i - 1][j - v[i])，可以看到：

求解第 i 行每个格子的值时，只依赖于第 i-1 行的值，并且只依赖于第 i-1 行的第 j 个值和第 j - v[i] 个值（分别对应第 i 个不选和选的两种情况
也就是说，只依赖于「上一个格子的位置」以及「上一个格子的左边位置」。

因此，只要我们将求解第 i 行格子的顺序「从 0 到 j 」改为「从 j 到 0」，就可以将原本 2 行的二维数组压缩到一行（转换为一维数组）。

参考 https://www.acwing.com/solution/content/1374/

1
2
3
4
5
6
7
8


// 状态f[j]定义：NN 件物品，背包容量j下的最优解。
// 对于背包容量 j 的 枚举，必须从 m 开始
// 为什么一维情况下枚举背包容量需要逆序？
// 在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。
// 而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
for(int i = 1; i <= n; i++)
    for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后

衍生问题：背包必须放满

完全背包问题

参考 https://www.acwing.com/problem/content/3/

问题描述

完全背包问题：有 N 种物品和一个容量为 C 的背包，每种物品都有无限件。

第 i 件物品的体积是 v[i]，价值是 w[i]。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

其实就是在 0-1 背包问题的基础上，增加了每件物品可以选择多次的特点（在容量允许的情况下）。

思路分析

根据和 0-1 背包问题的基本思路，定义状态：

dp[i][j] 表示考虑前 i 个物品，放入一个容量为 j 的背包可以获得的最大价值

由于每件物品可以被选择多次，因此对于每个 dp[i][j] 而言，其值应该是以下所有可能方案的最大值：

选择 0 件物品的最大价值，即 dp[i-1][j]
选择 1 件物品的最大价值，即 dp[i-1][j - v[i]] + w[i]
选择 2 件物品的最大价值，即 dp[i-1][j - 2 * v[i]] + 2 * w[i]
…
选择 k 件物品的最大价值，即 dp[i-1][j - k * v[i]] + k * w[i]

我们可以写成如下的状态转移方程：

dp[i][j] = max(dp[i - 1][j- k*v[i]] + k * w[i]), 0 <= k * v[i] <= j

这时候计算某个格子的值不再是常数操作。时间复杂度为 $O(N * C * C)$ 。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int dp[N][N], v[N], w[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ ) {
            dp[i][j] = dp[i-1][j]; // 选择 0 个 物品 i
            for(int k = 1; k * v[i] <= j; k ++ )
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
        }

    cout << dp[n][m] << endl;
}

进一步优化

使用上述三层循环是时间复杂度较高，可以进一步优化。对于 0/1 背包，由于推第 i 行的 dp [j] 时需要第 i - 1 行的 dp [j-v [i]] ，确保第 i 个物品还没有被使用过。因此忌讳在推导 dp [j] 时，dp [j-v [i]] 已经更新过了，这是 01 背包不希望发生的事，解决的办法就是 j 从大往小推。

对于完全背包问题，经常看到这样的讲解：

01 背包将容量维度「从大到小」遍历代表每件物品只能选择一件，而完全背包将容量维度「从小到大」遍历代表每件物品可以选择多次。

下面是数学证明：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int dp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++ ){
        for(int j = v[i]; j <= m; j ++ ){
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
}

多重背包问题

路径问题

Unique Paths II

思路分析

定义状态函数：

定义 dp[i][j] 表示走到坐标 (i, j) 的走法数

初始化：

第 1 列的格子只有从其上边格子走过去这一种走法，因此初始化 dp[i][0] 值为 1，存在障碍物时为 0；

第 1 行的格子只有从其左边格子走过去这一种走法，因此初始化 dp[0][j] 值为 1，存在障碍物时为 0。

1
2
3
4
5
6
7
8


int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
    dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
    dp[0][j] = 1;
}

状态转移：

如果 grid[i][j] 无障碍物：
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
否则：dp[i][j] = 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
25
26
27


class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }

        // 定义 dp 数组并初始化第 1 行和第 1 列。
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        // 根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

回文问题

Longest Palindromic Substring

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3


Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

思路分析

定义状态函数：

定义 dp[i][j] 表示字符串的子串 s(i, j) 为回文串的长度，如果不是回文串则为0

初始化：

矩阵全部初始化为 0
dp[i][i] 为 1

状态转移：

如果 s[i] == s[j]
- 如果 j - i == 1，则 dp[i][j] = 2
- 如果 j - i >= 2，则 dp[i][j]= dp[i+1][j-1] + 2
否则：dp[i][j] = 0
注意计算顺序，因为 dp[i][j] 会依赖于 dp[i+1][j-1]，要从后往前算

参考代码

 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


class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        if (size <= 1) return s;

        // default zero
        vector<vector<int> > dp(size, vector<int>(size, 0));
        int maxHead = 0;
        int maxSize = 1;

        for (int i = 0; i < size; i++) {
            dp[i][i] = 1;
        }

        for (int i = size-2; i >= 0; i--) {
            for (int j = i+1; j < size; j++) {
                if (j - i >= 2) {
                    if (s[i] == s[j]) {
                        if (dp[i+1][j-1] > 0) {
                            dp[i][j] = dp[i+1][j-1] + 2;
                        }
                    }
                } else {
                    dp[i][j] = s[i] == s[j] ? 2 : 0;
                }
                if (dp[i][j] > maxSize) {
                    maxSize = dp[i][j];
                    maxHead = i;
                }
            }
        }
        return s.substr(maxHead, maxSize);
    }
};

Longest Palindromic Subsequence

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb"

思路分析

定义状态函数：

定义 dp[i][j] 表示字符串的子串 s(i, j) 为回文子序列的长度，如果不是回文串则为0

初始化：

矩阵全部初始化为 0
dp[i][i] 为 1

状态转移：

如果 s[i] == s[j]
- 如果 j - i == 1，则 dp[i][j] = 2
- 如果 j - i >= 2，则 dp[i][j]= dp[i+1][j-1] + 2
否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
注意计算顺序，因为 dp[i][j] 会依赖于 dp[i+1][j-1]，要从后往前算

参考资料

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s[i];
            for (int j = i + 1; j < n; j++) {
                char c2 = s[j];
                if (c1 == c2) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

Palindrome Partitioning

Palindrome Partitioning II

Count Different Palindromic Subsequences

字符串编辑

Edit Distance

题目描述

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

1
2
3
4
5
6
7
8


Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

思路分析

定义状态函数：

定义 dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数。

初始化：

需要考虑 word1 或 word2 一个字母都没有，即全增加/删除的情况，所以预留 dp[0][j] 和 dp[i][0]

状态转移：

增：dp[i][j] = dp[i][j - 1] + 1
删：dp[i][j] = dp[i - 1][j] + 1
改：dp[i][j] = dp[i - 1][j - 1] + 1，如果 word1[i] == word2[j]，则 dp[i][j] = dp[i - 1][j - 1]
按顺序计算：当计算 dp[i][j] 时，dp[i - 1][j] ， dp[i][j - 1] ， dp[i - 1][j - 1] 均已经确定了
状态转移方程：新的 dp[i][j] 为三种情况下的最小值

参考代码

 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


class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));

        dp[0][0] = 0;
        for (int i = 1; i < m+1; i++) {
            dp[i][0] = i;
        }

         for (int j = 1; j < n+1; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                int d1 = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : dp[i-1][j-1] + 1;
                int d2 = dp[i-1][j] + 1;
                int d3 = dp[i][j-1] + 1;

                dp[i][j] = min(d1, min(d2, d3));
            }
        }
        return dp[m][n];
    }
};

221. 最大正方形

 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


class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
};