力扣

763. 划分字母区间

挺有意思的贪心，看起来挺好想，但我就是没想出来。

思路

我们先遍历一遍数组，用表记录下每个字母出现的最后一个位置。

unordered_map<char, int> hash_map;
int n = s.size();
for (int i = 0; i < n; i++) {
    hash_map[s[i]] = i;
}

然后我们再次遍历，从左往右，当前要被划分的子串的右边界即为里面字母结束的最远处。当我们到达最远处时，就结束划分，进入下一个子串。

int right = 0;
int left = 0;
vector<int> ans;
for (int i = 0; i < n; i++) {
    right = max(right, hash_map[s[i]]);
    if (i == right) {
        ans.push_back(right - left + 1);
        left = i + 1;
    }
}
return ans;

就这么简单。。。

139. 单词拆分

思路

直接给递推方程。

$$dp[i] = dp[j] \land s[j..i−1] \in wordDict， j < i$$

只需要遍历所有小于$i$的$j$即可得到dp[]。我们还可以剪枝，记录下wordDict[]中最长字符串的长度maxLen，我们可以保证$max(i - maxLen, 0) \leq j < i$。

答案

bool wordBreak(string s, vector<string>& wordDict) {
    int max_len = ranges::max(wordDict, {}, &string::length).length();
    unordered_set<string> words(wordDict.begin(), wordDict.end());

    int n = s.length();
    vector<int> dp(n + 1);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = i - 1; j >= max(i - max_len, 0); j--) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

152. 乘积最大子数组

不是那么常规公式化的一道题，需要变通一下。

思路

如果直接存最大乘积然后$f_{max}​(i)=max^{i=1}_n(f(i−1)\times a_i​,a_i​)$，我们会发现处理不了负数的情况。所以我们还需要一个数组$f_{min}(i)$存最小乘积。这样我们有

$$f_{max}​(i)=max^{i=1}_n(f_{max}​(i - 1)\times a_i​, f_{min}​(i-1) \times a_i,a_i​) \newline f_{min}​(i)=min^{i=1}_n(f_{max}​(i - 1)\times a_i​, f_{min}​(i-1) \times a_i,a_i​)$$

我们通过滚动数组技巧，避免再开设两个数组，直接用maxDp和minDp变量来记录即可。

解答

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    long maxDp = nums[0], minDp = nums[0], ans = nums[0];
    for (int i = 1; i < n; i++) {
        long mxd = maxDp;
        long mnd = minDp;
        maxDp = max(mxd * nums[i], max((long)nums[i], nums[i] * mnd));
        minDp = min(mxd * nums[i], min ((long)nums[i], mnd * nums[i]));
        if (minDp < INT_MIN) {
            minDp = nums[i];
        }
        ans = max(maxDp, ans);
    }
    return ans;
}

416. 分割等和子集

多维动态规划问题

思路

用二维数组dp[i][j]表示从数组的 $[0,i]$ 下标范围内选取若干个正整数（可以是 $0$ 个），是否存在一种选取方案使得被选取的正整数的和等于 $j$。

$$dp(i, j) = \begin{cases} dp[i - 1][j] || dp[i - 1][j - nums[i]], & j \geq nums[i] \\ dp[i - 1][j], & otherwise \end{cases}$$

状态转移方程较为简单，但是需要注意处理特殊情况。

• 数组长度必须为偶数
• 数组元素和必须为偶数
• 数组最大数必须小于元素和一半

如果不满足上述条件，答案皆为false。

72. 编辑距离

得做reduction，不然没法做

思路

我们发现问题可以等价为以下问题：

• 在任意一字符串插入字符
• 修改字符

他们都是消耗一次“编辑距离”。我们用 D[i][j] 表示 A 的前 $i$ 个字母和 B 的前 $j$ 个字母之间的编辑距离。

状态转移方程如下

$$dp(i, j) = \begin{cases} min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] - 1) + 1, & word1[i - 1] = word2[j - 1] \\ min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1, & otherwise \end{cases}$$

答案

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    if (!(m && n))
        return m + n;

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int left = dp[i - 1][j] + 1;
            int down = dp[i][j - 1] + 1;
            int left_down = dp[i - 1][j - 1];
            if (word1[i - 1] != word2[j - 1]) left_down += 1;
            dp[i][j] = min(left, min(down, left_down));
        }
    }
    return dp[m][n];
}