【刷题DAY46】139, 236.md

发表于 | 分类于

139.单词拆分

题目链接：https://leetcode.cn/problems/word-break/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 是求排列
  • dp[j]: 字符串长度为j的话，dp[j]为true，表示可以拆分为一个或多个在字典中出现的单词
  • 如果dp[j]是True, [j, i]区间的子串出现在字典里，那么dp[i]一定是true。
    1
    2
    3
    4
    5
    6
    for j in range(1, len(s)+1):    # 背包
        for word in wordDict:        # 物品
            # 如果dp[j]是True, [j, i]区间的子串出现在字典里，那么dp[i]一定是true。（j < i)
            if(j >= len(word)):
                if(dp[j - len(word)] and word == s[j - len(word):j]):
                    dp[j] = True
  • dp[0]为True，其余为False
  • 求排列问题，背包放外层，物品放内层，从前向后遍历

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 递推公式
    • 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
    • 问装满背包有几种方法：dp[j] += dp[j - nums[i]]
    • 问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]]
    • 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
  • 遍历顺序
    • 01背包
      • 一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历
    • 完全背包
      • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
      • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

复习

  • day20
    • 二叉树的最近公共祖先
      • 太久没做递归 又陷入一直想一直想的怪圈了

待重点复习

139, 236