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

139. 单词拆分

解题方法

思路:单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词,说明就是一个完全背包!
解法:

  • 定义i, j双指针利用滑动窗口逻辑遍历字符串,判断窗口字符串是否在字典内存在,如果存在则记录dp[i] = true,标记从0开始到i,这段字符串存在于字典内,保证字符串的一个连续性验证代码随想录算法训练营第三十七天 | leetcode:单词拆分,背包问题总结
  • 标记前一段字符串是否在字典内,这个动作很重要!用题目示例3做反例:如果没有标记前一段字符串是否存在字典,那么当i,j窗口遍历到dog这个词的时候,会标记dp[9] = true;但是dog之前的字符串catsan,却不存在字典内。
    输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false
  1. dp数组的含义:dp[i]:长度为i的字符串,dp[i]为true,表示可以拆分成一个或多个在字典出现的单词
  2. 确定递推公式:如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。
    所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
  3. 初始化dp数组:从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。
  4. 遍历顺序:拿 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)

背包问题总结

解题步骤

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

背包递推公式

  1. 问背包装满最大价值?递推公式: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的价值。
  2. 问能否能装满背包(或者最多装多少):dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])。
    对应题目如下:
    动态规划:416.分割等和子集
    动态规划:1049.最后一块石头的重量 II
    • 其中nums是题目给定的物品数值,物品价值与重量都是nums[i],属于第一种的变式。
  3. 问装满背包有几种方法:dp[j] += dp[j-nums[i]];
    对应题目如下:
  1. 问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
    对应题目如下:

遍历顺序

  1. 01背包:使用二维dp数组解题时,可以颠倒物品与背包的遍历顺序,但是使用一维数组解题时,只能先遍历物品再遍历背包容量,且第二层for循环是从大到小倒序遍历,以此来保证物品只被使用了一次。
  2. 完全背包:
    如果求组合数就是外层for循环遍历物品,内层for遍历背包。
    如果求排列数就是外层for遍历背包,内层for循环遍历物品。
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!