Loading [MathJax]/jax/output/HTML-CSS/jax.js

「数据结构与算法」- 动态规划

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 1.5k | 阅读时间 ≈ 6

动态规划思路

要用动态规划要具备两个性质，重叠子问题和最优子问题

  • 最优子问题：如果一个问题的最优解包含了其中子问题的最优解，那么称其有最优子结构
  • 重叠子问题：当解决一个问题时，往往依赖其更小规模的子问题的解，甚至依赖与若干个规模更小的子问题的解。

如果一个问题满足这两个条件，就可以用动态规划的方法去求解。对于动态规划问题，最难的就是列出状态转移方程。可以参考下面的方式来分解问题：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组 / 函数的含义

动态规划题目

最长回文子串

问题描述

leetcode #5
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

解题思路

这一题里面的状态 dp[i][j] 代表了字符串 s[i:j] 是否是回文子串。初始的状态 dp[i][i] 都为 true，dp[i][i+1] 则要判断下字符 s[i] 和 s[i+1] 是否相等。
状态转移方程则为：
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
这里需要注意的一个点是，遍历不能直接用 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
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp (n, vector<bool> (n, false));
        if (n == 0) return "";

        int max_count = 1;
        string res;
        res = s[0];

        // base case
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        for (int i = 0; i < n-1; i++){
            if (s[i] == s[i+1]){
                dp[i][i+1] = true;
                max_count = 2;
                res = s.substr(i,2);
            }
        }
        // dp
        for (int l = 2; l < n; l++){
            for (int i = 0; i < n; i++){
                int j = i + l;
                if (j >= n) break;
                if (dp[i+1][j-1] && s[i] == s[j]){
                    dp[i][j] = true;
                    if (l+1 > max_count){
                        res = s.substr(i,l+1);
                        max_count = l;
                    }
                }
            }
        }
        return res;
    }
};

不过这样也还是超时了，这题也太容易超时了吧。

子集和问题

问题描述

给定一个正整数集合 S 和一个正整数 M，是否在 S 中存在子集使得子集之和等于 M。
例如:
[1,2,6,3,17,82,23,234] -> 26
Solution [0,1,6]

[1,2,6,3,17,82,23,234] -> 40
Solution [4,6]

[1,2,6,3,17,82,23,234] -> 23
Solution [6]

解题思路

对于这个问题，难点同样在于列出状态转移方程。首先我们应该先明确状态。对于一个集合 S=a1,a2,…,an 中的每一个元素，都存在两种状态取和不取，再考虑他们的和是否等于 M，但是这样的情况就有 2n。所以要换个思路，令 dp[i][j] 代表前 i 个元素中是否存在子集使得子集和等于 j。那么对于 dp[i][j] 则有两种情况:

  • 如果 S[i] > j，那么 i 一定是不再子集中的，所以 dp[i][j]=dp[i-1][j]，即当前数大于子集和的目标数，那么当前数对于子集和能否等于目标数没有影响，所以当前状态（dp[i][j]) 应该是等于不包含 S[i] 时的状态（dp[i-1][j]）。
  • 如果 S[i] <= j，也存在两种情况：S[i] 不在子集中，那么 dp[i][j]=dp[i-1][j]；如果 S[i] 在子集中，那么它的状态应该和上一个状态并且目标数等于 j-S[i] 时的状态相等，即 dp[i][j] = dp[i-1][j-S[i]]。

所以可以列出状态转移方程：

1
2
3
4
if (S[i] > j)
    dp[i][j] = dp[i-1][j]
else if (S[i] <= j)
    dp[i][j] = dp[i-1][j] || dp[i-1][j-S[i]]

程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<bool> > dp(nums.size()+1, vector<bool> (target+1, false));
// base case
// i=0的时候代表是空集
// j=0的时候代表要求的和也是空集，所以都为true
for (int i = 0; i < nums.size()+1; i++)
    dp[i][0] = true;
// dp
for (int i = 1; i < nums.size()+1; i++){
    for (int j = 1; j < target+1; j++){
        if (j < nums[i-1])
            dp[i][j] = dp[i-1][j];
        else if (j - nums[i-1] >= 0)
            dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
    } 
}

如果想要找到对应的子集中的元素的序号，那么可以通过以下方法：

首先我们知道如果 dp[i][j]=dp[i-1][j]=true，那么这代表 S[i] 不在子集中；但是如果 dp[i][j]=true，[i-1][j]=false 那么 S[i] 则一定在子集中，那么我们就可以找到一个子集中的元素 S[i] 了。又因为 S[i] 在子集中，那么如果排除掉 S[i]，剩下的需要求的子集和就变成 j-S[i]，所以我就接着从 dp[i-1][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
29
30
31
32
vector<int> sum_problem(vector<int> nums, int target){
    // init
    vector<vector<bool> > dp(nums.size()+1, vector<bool> (target+1, false));
    for (int i = 0; i < nums.size()+1; i++)
        dp[i][0] = true;
    // dp
    for (int i = 1; i < nums.size()+1; i++){
        for (int j = 1; j < target+1; j++){
            if (j < nums[i-1])
                dp[i][j] = dp[i-1][j];
            else if (j - nums[i-1] >= 0)
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
        } 
    }
    vector<int> res;
    if (!dp[nums.size()][target])
        return res;
    else
    {
        int sum = target;
        while(sum != 0){
            for (int i = nums.size(); i >= 1; i--){
                if (dp[i][sum] == 1 && dp[i-1][sum] == 0){
                    res.push_back(i-1);
                    sum -= nums[i-1];
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
}

参考资料

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie
https://www.bilibili.com/video/av38722679

子集和问题:
https://www.cnblogs.com/yulinfeng/p/7106564.html
https://zhuanlan.zhihu.com/p/37822898