LeetCode 139 完全平方数

题目链接：139. 单词拆分 - 力扣（LeetCode）

【解题思路】

• 1.确定dp数组以及下标含义

  • dp[j]的定义是：

    • 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词

  • 最终要返回的是dp[s.size]

• 2.确定递推公式

  • 如果j到i这个区间出现在单词里，同时dp[j]==true的话

    • dp[i]=true

• 3.确定dp数组如何初始化

  • dp[0]=true

• 4.确定遍历顺序

  • 先遍历背包：

    • 再遍历物品：

      • 递推公式

  • Carl说先遍历物品是组合数，先遍历背包是排列数，对于这点，我的理解是：

    • 先遍历物品后遍历背包：

      • 1）外层固定物品1，进入内层循环

      • 2）背包容量不断增加

        • 物品1被重复添加进不同容量的背包中，直到背包容量遍历完毕

      • 3）背包容量遍历完毕后，执行下一次循环，开始添加物品2

        • 物品1已经被添加进每一个不同容量的背包里，因此物品2肯定会在物品1之后

    • 先遍历背包后遍历物品：

      • 1）外层循环固定背包容量

        • 在大小固定的背包里循环遍历添加物品，直到物品全遍历一次

      • 2）物品遍历结束，外层背包容量+1

        • 此时仍要执行内层循环，再次遍历一遍物品

        • 可能会出现如下情况：

          • 在上一轮遍历到物品3时，当前容量的背包已经没有办法塞入物品3，因此背包里此时有物品1和物品2

            • 在当前轮遍历的时候发现增加了容量的背包可以再添加一个物品1，就会有【物品1，物品2，物品1】这样的情况，所以很可能会有物品1出现在物品2之类的情况

  • 本题的单词顺序有着重要作用，因此可以看成求排列数，先遍历背包

• 5.举例推导dp数组

  • 手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移

【解题步骤】

• 1.创建一个HashSet，放wordDict

• 2.新创建一个布尔类型的数组v，长度为字符串的长度+1

• 3.初始化v[0]为true

• 4.求排列数

  • 先遍历物品

    • 再遍历背包

      • 递推公式

• 4返回

  • return v[s.length()]

【代码部分】

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
		HashSet<String> set = new HashSet<>(wordDict);
		boolean[] v = new boolean[s.length()+1];
		v[0] = true;
		for(int i = 1 ; i <= s.length() ; i++){
			for(int j = 0 ; j <= i && !v[i] ; j++){
				if(set.contains(s.substring(j,i))&& v[j]){
					v[i] = true;
				}
			}
		}
		return v[s.length()];

    }
}