​ 对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。

279 完全平方数

给定一个正整数，求其最少可以由几个完全平方数相加构成。

输入是给定的正整数，输出也是一个正整数，表示输入的数字最少可以由几个完全平方数相加构成。

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

解析：

​ 设置状态：定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加构成

​ 状态转移方程：在本题中，位置 i 只依赖 i - k^2 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。因此数字 i 可以取的最小值为 dp[i] = 1 + min(dp[i-1], dp[i-4], dp[i-9], ....... )

​ 初始情况：0 无法由任一个完全平方数相加构成，即dp[0]=0

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i=1;i<=n;++i){
            for(int j=1;i-j*j>=0;++j){
                dp[i] = min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

343 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。

输入是给定的正整数，输出也是一个正整数，表示输入的数字拆分获得的最大乘积。

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

解析：

​ 本题和279题相似，位置 i 依赖于 i - j 的位置

​ 设置状态：定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 拆分可以获得的最大乘积

​ 状态转移方程：将 i 拆分分为两种情况，第一种是仅拆分为两个数即 i 和 i - j，不再拆分为更多正整数，这种情况的乘积为 j*(i-j)；第二种是拆分出第一个正整数 j 后，将 i - j 继续拆分为多个正整数，这种情况乘积为j*dp[i-j]。所以在拆分的第一个数 j 固定的情况下状态转移方程为dp[i] = max(j*(i-j),j*dp[i-j])。由于 j 的取值范围是 1 到 i - 1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))。

​ 初始情况：0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0] = dp[1] = 0

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        for(int i=2;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

91 解码方法

已知字母 A-Z 可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个数字串。

输入是一个由数字组成的字符串，输出是满足条件的解码方式总数。

输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6)

解析：

​ 本题的特殊情况较多因为只有 1-26 可以表示字母，所以对于一些特殊情况，比如数字 0 或者当相邻两数字大于 26 时，需要有不同的状态转移方程。本人对此题还存在一些疑惑，仅贴出代码，欢迎解惑。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        if(n==0){
            return 0;
        }
        int prev = s[0] - '0';
        if(!prev){
            return 0;
        }
        if(n==1){
            return 1;
        }
        vector<int> dp(n+1,1);
        for(int i=2;i<=n;++i){
            int cur = s[i-1] - '0';
            if((prev==0 || prev>2) && cur == 0){
                return 0;
            }
            if((prev < 2 && prev>0) || prev == 2 && cur < 7){
                if(cur){
                    dp[i] = dp[i-2] + dp[i-1];
                }else{
                    dp[i] = dp[i-2];
                }
            }else{
                dp[i] = dp[i-1];
            }
            prev = cur;
        }
        return dp[n];
    }
};

139 单词拆分

给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字符串都可以在集合内找到。

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”；注意你可以重复使用字典中的单词。

解析：

​ 本题类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。

​ 设置状态：用一个一维数组 dp[i] 表示开头到以 i 位置结束的子串是否能够在集合中找到

​ 状态转移方程：如果开头到以 j 结尾的子串都能在集合中找到，且从 j 到 i 的子串也能够在集合中找到那么 dp[i] = true

​ 初始情况：字符串和集合都为空时为真，dp[0]=true

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordDictSet;
        for(const auto w: wordDict){
            wordDictSet.insert(w);
        }
        int n = s.length();
        vector<bool> dp(n+1,false);
        dp[0] = true;
        for(int i=1;i<=n;++i){
            for(int j=0;j<i;++j){
                // 分割类型动态规划：dp[i] = s[0]到s[j-1]为true && s[j]到s[i-j]子串在字典中
                if(dp[j] && wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end()){
                    dp[i] = true;
                    // dp[i] 表示的是 s[0]到s[i-1]的子串中单词是否出现在字典中
                    break;
                }
            }
        }
        return dp[n];
    }
};

参考资料

LeetCode 101：和你一起轻松刷题(C++) 第 7 章 深入浅出动态规划