DP - Cut Sequence

Algorithms
dp
Catalogue
  1. 1. Analysis
    1. 1.1. Question Type
      1. 1.1.1. Solution Type
  2. 2. Split Array
    1. 2.1. 410. Split Array Largest Sum
      1. 2.1.1. Solution1. DP
      2. 2.1.2. Solution2. Binary Search
  3. 3. Split String
    1. 3.1. 139. Word Break
      1. 3.1.1. Solution1. DFS
      2. 3.1.2. Solution2. DP
    2. 3.2. 140. Word Break II
    3. 3.3. 91. Decode Ways
    4. 3.4. 639. Decode Ways II
    5. 3.5. 132. Palindrome Partitioning II
    6. 3.6. 410. Split Array Largest Sum

Analysis

Question Type

  • Seperate an sequence to several nonoverlapping subarray
  • no limit or limited k on the number of the subarray
  • Each subarray meet or meet some requirement!

Solution Type

  • Normally, dp[i][j]represents previous i elements seperate k subarray

Split Array

410. Split Array Largest Sum

Solution1. DP

  • DP[i][j] represents that the largest sum for previous i elements seperated to j group
  • DP[i][j] = min{max{dp[k][j-1], sum(k+1, i)}} ($0<= k <i$)
  • Time : O($mn^2$), Space : O(mn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution:
        def splitArray(self, nums, m):
            n = len(nums)
            # Prefix Sum
            preSum = [0]
            for i in range(n):
                preSum.append(preSum[-1] + nums[i])

            dp = [[float('inf')] * m for _ in range(n+1)]

            # Init
            dp[0][0] = 0
            for i in range(n+1):
                dp[i][0] = preSum[i]
            for j in range(m):
                dp[0][j] = 0

            # DP
            for i in range(1, n+1):
                for j in range(i):
                    for k in range(1, m):
                        dp[i][k] = min(dp[i][k], max(dp[j][k-1], preSum[i]-preSum[j]))
            return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def splitArray(self, nums, m):
        start, end = max(nums), sum(nums)
        while start < end:
            mid = start + (end - start) // 2
            if self.isValid(mid, nums, m):
                end = mid
            else:
                start = mid + 1
        return start

    def isValid(self, mid, nums, m):
        cur = 0
        cnt = 0
        for num in nums:
            cur += num
            if cur > mid:
                cur = num
                cnt += 1
                if cnt >= m:
                    return False
        return True

Split String

139. Word Break

Solution1. DFS

  • TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # Worst Case : Time O(n!)
    class Solution(object):
        def wordBreak(self, s, wordDict):
            wset = set(wordDict)
            return self.isWordBreak(s, wset)

        def isWordBreak(self, s, wset):
            if len(s) == 0:
                return True

            for i in xrange(len(s)):
                if s[i:] in wset:
                    if self.isWordBreak(s[:i], wset):
                        return True
            return False

Solution2. DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Time : O(n^2)
class Solution(object):
    def wordBreak(self, s, wordDict):
        wset = set(wordDict)
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True

        for i in xrange(n):
            for j in xrange(i+1):
                if s[j:i+1] in wset and dp[j]:
                    dp[i+1] = True
                    break
        return dp[-1]

140. Word Break II

  • DFS + Memorization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def wordBreak(self, s, wordDict):
        words = set(wordDict)
        return self.dfs(s, words, {})

    def dfs(self, s, words, dic):
        if len(s) == 0:
            return ['']

        if s in dic:
            return dic[s]

        res = []
        for i in xrange(len(s)):
            if s[:i+1] in words:
                ans = self.dfs(s[i+1:], words, dic)
                for item in ans:
                    if item == '':
                        res.append(s[:i+1])
                    else:
                        res.append(s[:i+1] + ' ' + item)
        dic[s] = res
        return res

91. Decode Ways

  • care about edge cases
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution(object):
        def numDecodings(self, s):
            n = len(s)
            dp = [0] * n
            dp[0] = 1 if s[0] != '0' else 0
            for i in range(1, n):
                # case1 : 1 letter
                if s[i] != '0':
                    dp[i] += dp[i-1]

                # case2 : 2 letter
                if 10 <= int(s[i-1:i+1]) <= 26:
                    dp[i] += dp[i-2] if i >= 2 else 1
            return dp[-1]

639. Decode Ways II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def numDecodings(self, s):
        MOD = 10**9 + 7
        e0, e1, e2 = 1, 0, 0
        for c in s:#xrange(len(s)):
            if c == '*':
                f0 = 9*e0 + 9*e1 + 6*e2
                f1 = e0
                f2 = e0
            else:
                f0 = (c!='0')*e0 + e1 + (c<='6')*e2
                f1 = (c=='1')*e0
                f2 = (c=='2')*e0
            e0, e1, e2 = f0 % MOD, f1, f2
        return e0

132. Palindrome Partitioning II

  • isPalindrome can also use the DP way to solve!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def minCut(self, s):
        if len(s) == 0:
            return 0

        n = len(s)
        isPalin = [[False] * n for _ in range(n)]
        for j in range(n):
            for i in range(j, -1, -1):
                if s[i] == s[j] and (j-i <= 2 or isPalin[i+1][j-1]):
                    isPalin[i][j] = True

        dp = [n-1] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for j in range(i):
                if isPalin[j][i-1]:
                    if j == 0:
                        dp[i] = 0
                    else:
                        dp[i] = min(dp[i], dp[j] + 1)
        return dp[-1]

410. Split Array Largest Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def splitArray(self, nums, m):
        n = len(nums)
        if m >= n:
            return max(nums)

        dp = [[float('inf')] * m for _ in range(n)]
        for k in range(m):
            dp[0][k] = nums[0]

        pre_sum = [0]
        cur = 0
        for i in range(n):
            cur += nums[i]
            pre_sum.append(cur)
            dp[i][0] = cur

        for i in range(1, n):
            for j in range(i):
                for k in range(1, m):
                    dp[i][k] = min(dp[i][k], max(dp[j][k-1], pre_sum[i+1]-pre_sum[j+1]))

        return dp[-1][-1]
Share