Day 18 | 8/28

[tech-cow]

今日计划 | DP基础

Leetcode

• 139. Word Break
• 120. Triangle
• 64. Minimum Path Sum
• 343 Integer Break
• 279 Perfect Squares
• 62 Unique Paths
• 63 Unique Paths
• 309 Best Time to Buy and Sell Stock w/ CD

[tech-cow]

Leetcode

139. Word Break

类型：一维DP
Time Complexity O(N^2)
Space Complexity O(N)

class Solution(object):
    def wordBreak(self, s, wordDict):
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1,n+1):
            for j in range(0, i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]  # or dp[n]

因为我们创建的DP数组长度比原字符串长度大于一，所以对python slicing为什么用s[j:i] 而不是s[j+1:i] 的小伙伴们(也就是我本人- -)，这里只要在dp[i] = True 的代码下面debug下，就知道到底发生了什么

print(j, i)
print(s[j:i])
print(dp)

测试结果如下

j, i = 0 4
s[j:i] = 'leet'
dp = [True, False, False, False, True, False, False, False, False]

j, i = 4 8
s[j:i] = code
dp = [True, False, False, False, **True**, False, False, False, True]