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

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 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={a_1,a_2,…,a_n}$中的每一个元素，都存在两种状态取和不取，再考虑他们的和是否等于M，但是这样的情况就有$2^n$。所以要换个思路，令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