问题描述

  1. 给定一个非空字符串s，以及一个包含非空单词列表的字典，判断s是否可以被空格拆分为一个或多个在字典中出现的单词。
  2. https://leetcode-cn.com/problems/word-break/

思路描述

  1. 本质就是单词拆分，如果要求出所有的单词拆分的情况，就需要利用回溯的方法了。
  2. 但是回溯的方法复杂度太高了，而且也只需要是否存在这样的拆分，而不需要记录所有的拆分情况，所以利用动态规划解决
  3. 其实在写回溯的实现时，已经意识到可以用动态规划了，因为其中有太多重复操作。
  4. 动态规划
    • 寻找最优子结构
    • 理解dp数组
    • 理解循环过程，最好为循环的每个指针赋予一个意义，比如这道题里面，外层循环指针代表字符串长度，内存循环指针代表单词长度。