代码随想录算法训练营第四十六天|139.单词拆分、背包问题总结
LeetCode 139. 单词拆分
题目链接：139. 单词拆分 - 力扣（LeetCode）
这道题使用完全背包来实现，我们首先考虑字符串是否可以由字符串列表组成，因此dp数组大小为n + 1 ，其意义是，在n个位置时是否能拼接成功。因此，当前n状态由前面状态所转移确定。
每道题都要考虑dp五步：
1）确定dp数组下标与值的关系：处于n位时是否能拼接成功。
2）确定递推公式：我们把n个数的状态，看作i之前j到i的字母是否能在字符串列表中存在
3）确定初始值：dp[0]为1,没得选
4）确定遍历的数：注意一下边界问题
5）带入验证一下
代码：
#python //一维DP
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [0 for _ in range(n + 1)]
dp[0] = 1 //由空集可以组成
for i in range(1, n + 1):
for j in range(i + 1): //注意i与j的位置来确定在字符串中子串的边界，从而来判断是否在列表中
if dp[j] == 1 and str(s[j : i]) in wordDict:
dp[i] = 1 //满足
return bool(dp[n]) //返回布尔值