代码随想录算法训练营第三十八天 | leetcode：单词拆分,背包问题总结

_zzh 的个人博客 / 28 / 0 / 创建于 1个月前 / 更新于 1个月前

139. 单词拆分

解题方法

思路：单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词，说明就是一个完全背包！
解法：
定义i, j双指针利用滑动窗口逻辑遍历字符串，判断窗口字符串是否在字典内存在，如果存在则记录dp[i] = true，标记从0开始到i,这段字符串存在于字典内，保证字符串的一个连续性验证
标记前一段字符串是否在字典内，这个动作很重要！用题目示例3做反例：如果没有标记前一段字符串是否存在字典，那么当i，j窗口遍历到dog这个词的时候，会标记dp[9] = true;但是dog之前的字符串catsan，却不存在字典内。
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
dp数组的含义：dp[i]：长度为i的字符串，dp[i]为true，表示可以拆分成一个或多个在字典出现的单词
确定递推公式：如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
初始化dp数组：从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。
遍历顺序：拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。
“apple”, “pen” 是物品，那么我们要求物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。所以这题是求排列数，求排列数就是外层for遍历背包，内层for循环遍历物品。

code

class Solution {

    /**
     * @param String $s
     * @param String[] $wordDict
     * @return Boolean
     */
    function wordBreak($s, $wordDict) {
        $dp = [];
        $len = strlen($s);
        for($i = 0; $i <= $len; $i++){
            $dp[$i] =  false;
        }
        $dp[0] = true;
        //注意这里是<=len,因为dp[1]才开始对照字符串
        for($i = 1; $i <= $len; $i++){
            for($j = 0; $j < $i; $j++){
                //截取字符串
                $str = substr($s, $j, $i - $j);
                //print_r([$i, $j, $str]);
                //$dp[$j] == true 标记前一段字符串是否存在字典内
                if(in_array($str, $wordDict) && $dp[$j] == true){
                    // print_r("******");
                    // print_r([$i, $j, $str]);
                    $dp[$i] = true;
                    break;
                }
            }
        }
        //print_r($dp);
        return $dp[$len];
    }
}

复杂度

时间复杂度

O(n^3)，因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）

空间复杂度

O(n)

背包问题总结

解题步骤

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

背包递推公式

问背包装满最大价值？递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + val[i])。
对应题目如下：
动态规划：474.一和零（虽然为二维的变式）

dp[j]为未放入物品i的状态；因为是滚动数组，下一轮的值是上一轮的值拷贝下来的。
dp[j-weight[i]] + val[i]为放入物品i的状态。

j-weight[i]：表示背包容量减去物品i的重量（因为放进背包里面，所以背包容量要减少）
val[i]：表示物品i的价值。

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])。
对应题目如下：
动态规划：416.分割等和子集
 动态规划：1049.最后一块石头的重量 II

其中nums是题目给定的物品数值，物品价值与重量都是nums[i],属于第一种的变式。

问装满背包有几种方法：dp[j] += dp[j-nums[i]];
对应题目如下：

动态规划：494.目标和(opens new window)
动态规划：518. 零钱兑换 II(opens new window)
动态规划：377.组合总和Ⅳ(opens new window)
动态规划：70. 爬楼梯进阶版（完全背包）

其中dp[j-nums[i]]，代表当前容量为j-nums[i]的背包，装满有几种方式。这么说有点抽象。图示：

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
对应题目如下：

动态规划：322.零钱兑换(opens new window)
动态规划：279.完全平方数

遍历顺序

01背包：使用二维dp数组解题时，可以颠倒物品与背包的遍历顺序，但是使用一维数组解题时，只能先遍历物品再遍历背包容量，且第二层for循环是从大到小倒序遍历，以此来保证物品只被使用了一次。
完全背包：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

算法 PHP面试