【划分型 DP-最优划分】力扣2707. 字符串中的额外字符

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符 最少 。

示例 1：
输入：s = “leetscode”, dictionary = [“leet”,“code”,“leetcode”]
输出：1
解释：将 s 分成两个子字符串：下标从 0 到 3 的 “leet” 和下标从 5 到 8 的 “code” 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。

示例 2：
输入：s = “sayhelloworld”, dictionary = [“hello”,“world”]
输出：3
解释：将 s 分成两个子字符串：下标从 3 到 7 的 “hello” 和下标从 8 到 12 的 “world” 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。

提示：
1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] 和 s 只包含小写英文字母。
dictionary 中的单词互不相同。

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<int> dp(n+1);
        for(int i = n-1; i >= 0; i--){
            dp[i] = dp[i+1] + 1;
            for(auto& word : dictionary){
                if(s.compare(i, word.size(), word) == 0){
                    dp[i] = min(dp[i], dp[i+word.size()]);
                }
            }
        }
        return dp[0];
    }
};

时间复杂度：O(N∗M∗K)
空间复杂度：O(N)

我们定义一个动态数组dp[i]，代表从dp[i,…,n-1]中未匹配的字符数量。我们倒序遍历，在每一次遍历的开始，我们需要初始化dp[i]，dp[i]的初始值可以由dp[i+1]+1状态转移而来。然后接下来我们通过遍历字典里的单词，s.compare(i, word.size(), word) == 0的含义是我们从s[i]开始的长度为word.size()的字符串是否和字典的单词匹配，如果匹配的话，并且dp[i+word.size()]小于dp[i]，就更新dp[i]为dp[i+word.size()]。

最后返回dp[0]，代表从字符串s的最少未匹配字符。