【算法】一维动态规划
2024-04-22 23:00:44 #算法

引子

动态规划永远是一道迈不过去的坎～

道理我都懂，但是相关的题目就是做不出来～

这种问题太灵活啦！

何为动态规划？

我曾经在上过“算法设计与分析”课程后，写过相关的文章：【算法】动态规划。

简单说来，动态规划这个名字本身没什么特殊的，可能就是某人为了装B而设计的：动态规划-历史。

动态规划本身是这样的一种方法：从小的子问题逐步求解，最终求解大的主问题的过程。直接求取这种“主问题”，往往会重复计算子问题，造成不必要的开销，若从子问题求解，并记住子问题的结果，就能在求取主问题时，节省大量的开销。

其步骤大概为：简化原问题-建立递归方程-求解子问题-求解原问题。其中，建立递归方程(建立递推公式)是最重要的一步。

简单应用可以参考我之前的博文，本文主要记录力扣上几类一维DP问题的思路、求解方法。

递推公式

递推公式：主问题和子问题有明显联系

主问题和子问题通过递推公式连接在一起，可以通过分析题目寻找这种关系。

对于Leetcode70. Climbing Stairs：

主问题不好直接求解，先从小问题考虑：上到第一层有一种走法，第二层有两种走法，那么可以在这个基础上推得：

单独拿每一层来分析，到达$i$层共有两种方法，从$i-1$层跨一级台阶走上来，或者从$i-2$层跨两级走上来，于是，令$dp[i]$为到达第$i$层的总共方法数，递推公式为：
$$
dp[i] = dp[i-1]+dp[i-2]
$$
对于Leetcode118. Pascal’s Triangle，联系已经非常明显了，令$dp[i][j]$为第$i$行第$j$列的元素，递推公式为:
$$
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
$$

递推公式：主问题和部分子问题有明显联系

主问题有时无法直接使用DP，需要拆分成部分子问题，对于这些子问题应用DP，最后合并。

对于Leetcode213. House Robber II来说，由于最后一个房子和第一个房子是邻接房子，不能直接使用Leetcode198. House Robber的直接递推DP，需要对于两个子问题进行DP：最终的最大值为不抢最后一个房子的值和不抢第一个房子的值的最大值。用类似Python表示方法来表示递推公式：
$$
dp[all]=max(dp[1:],dp[:-1])
$$
python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rob(self, nums: List[int]) -> int:
        return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1]))

    def helper(self, nums: List[int]):
        rob1, rob2 = 0, 0

        for n in nums:
            newRob = max(rob1 + n, rob2)
            rob1 = rob2
            rob2 = newRob
        return rob2

递推关系

有的时候递推公式并不是很好写出来，但是可以根据相关子问题的模式，获得主问题和子问题的关系，之后用代码实现这种关系即可。大多数问题都属于这样的问题。

对于Leetcode5. Longest Palindromic Substring最长回文子串问题，可以通过一维DP求解。

考虑回文串本身是如何构建的：

  1. 奇数长度的回文串，可以看作由中心字母向两边拓展而来，即：”c”->”aca”->”bacab”->”cbacabc”。
  2. 偶数长度的回文串，可以看作由空白字符向两边扩展而来，即：””->”cc”->”bccb”->”dbccbd”。

用上下文无关文法来表示:
$$
S\to aSa|bSb|\cdots|zSz|a|b|\cdots|z|\varepsilon
$$
那么可以使用$dp[i]$记录以$i$结尾的最长回文子串的起始索引，这样就相当于表示了现有的一串回文子串，在这个基础上拓展或修改，就可以得到全局的最长回文串：

一般的，当遍历到$dp[i+1]$时，如果$i+1$处的字符和$dp[i]-1$处相等，则表明可以扩展，让$dp[i+1]$为$dp[i]-1$即可:

若二者不相等，则遍历以$dp[i],dp[i]+1,dp[i]+2,\cdots$起始的所有子串，直到找到回文串。

可行的C++解法:

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:
    bool isPalindrome(string a) {
   
        for(int l = 0, r = a.size() - 1; l < r; l++, r--) {
            if(a[l] != a[r]) {
                return false;
            }
        }
             cout << a << endl;
        return true;
    }

    string longestPalindrome(string s) {
        vector<int> dp;
        dp.push_back(0);
        string result = "";
        result += s[0];
        for(int i = 1; i < s.size(); ++i) {
            if(dp[i-1] > 0 && s[dp[i-1] - 1] == s[i]) {
                dp.push_back(dp[i-1] - 1);
            } else {
                int l, r = i;
                for(l = dp[i-1]; l < r; ++l) {
                    if(isPalindrome(s.substr(l, r - l + 1))) {
                        break;
                    }
                }
                dp.push_back(l);
            }
            result = (i - dp[i] + 1) > result.size() ? s.substr(dp[i], i-dp[i]+1) : result;
        }
        return result;
    }
};
Prev
2024-04-22 23:00:44 #算法
Next