DP - Sequence

2018-08-13

Algorithms

Catalogue

Input is a single sequence, we should get the properties of previous i elements

state : dp[i] is previous i elements position/numbers/charaters
function : dp[i] = dp[j]… (j < i)
initialize : dp[0] … (means no element in the array)
answer : dp[n] …

Longest/Maximum Sequence

Sub-array: contiguous elements in an array，number is $n^2$
Sub-sequence: not necessarily contiguous，number is n!

674. Longest Continuous Increasing Subsequence

dp[i] = dp[i-1] + 1 if nums[i] > nums[i-1] else 1

# Time : O(n), Space : O(n)
class Solution(object):
    def findLengthOfLCIS(self, nums):
        if not nums: return 0

        n = len(nums)
        dp = [0] * n
        dp[0] = 1

        for i in xrange(1, n):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = 1
        return max(dp)

# Time : O(n), Space : O(1)
class Solution(object):
    def findLengthOfLCIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        res = 1
        cur = 1

        for i in xrange(1, n):
            if nums[i] > nums[i-1]:
                cur += 1
                res = max(res, cur)
            else:
                cur = 1
        return res

300. Longest Increasing Subsequence

dp[i] represents from the 0-the element to the i-th element, including the i-th element, the lenght of the longest ascending subsequence.

Base Case : dp[0] = 1
Induction Rule : dp[i] = max(dp[i], dp[j] + 1 if nums[i] > nums[j])

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

53. Maximum Subarray

State : dp[i] represents [from the 0-th element to the i-the element] the maximum sum of a subarray, including the i-th element.

class Solution(object):
    def maxSubArray(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [0] * n
        res = dp[0] = nums[0]
        for i in xrange(1, n):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
            res = max(res, dp[i])
        return res

Improve Space Complexity

what if we want to optimize the space complexity?

class Solution(object):
    def maxSubArray(self, nums):
        if not nums:
            return 0

        n = len(nums)
        res = cur = nums[0]
        for i in xrange(1, n):
            cur = max(nums[i], nums[i] + cur)
            res = max(res, cur)
        return res

What if we want you to return the start and end indices of the solution array?

when to move the start and end?
need another two variables sol_start, sol_end, instead of global max length

Path Search

State : dp[i] means ending with i

70. Climbing Stairs

class Solution(object):
    def climbStairs(self, n):
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in xrange(1, n):
            dp[i+1] = dp[i] + dp[i-1]
        return dp[-1]

746. Min Cost Climbing Stairs

State : dp[i] means the min cost to get stair[i]

class Solution(object):
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        dp = [0] * (n + 1)
        for i in xrange(2, n+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[-1]

403. Frog Jump

states are different! add a speed states!!!

class Solution(object):
    def canCross(self, stones):
        n = len(stones)
        dp = [set() for _ in range(n)]
        dp[0].add(1)

        for i in range(1, n):
            for j in range(i):
                gap = stones[i] - stones[j]
                if gap in dp[j]:
                    dp[i].add(gap - 1)
                    dp[i].add(gap)
                    dp[i].add(gap + 1)
        return len(dp[-1]) != 0

Prefix Sum

Given Array A[1..n]，Prefix Sum Array PrefixSum[1..n] defined as：
PrefixSum[i] = A[0]+A[1]+…+A[i-1]；

e.g. A[5,6,7,8] –> PrefixSum[5,11,18,26]
PrefixSum[0] =A[0] ;
PrefixSum[1] =A[0] + A[1] ;
PrefixSum[2] =A[0] + A[1] + A[2] ;
PrefixSum[3] =A[0] + A[1] + A[2] + A[3] ;

303. Range Sum Query - Immutable

Given an immutable array, call rangeSum multiple times!

class NumArray(object):
    # Time : O(n), Space : O(n)
    def __init__(self, nums):
        self.preSum = [0]
        n = len(nums)
        s = 0
        for i in xrange(n):
            s += nums[i]
            self.preSum.append(s)
    # Time : O(1)
    def sumRange(self, i, j):
        return self.preSum[j+1] - self.preSum[i]

Follow up : What if the array is mutable?

304. Range Sum Query 2D - Immutable

We use preSum trick in the array! How about the matrix?

class NumMatrix(object):
    # Time : O(mn), Space : O(mn)
    def __init__(self, matrix):
        if not matrix:
            self.dp = []
            return
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n+1) for _ in xrange(m+1)]
        dp = self.dp
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

    # Time : O(1)
    def sumRegion(self, row1, col1, row2, col2):
        if not self.dp:
            return 0
        return self.dp[row2+1][col2+1] - self.dp[row2+1][col1] - self.dp[row1][col2+1] + self.dp[row1][col1]

363. Max Sum of Rectangle No Larger Than K

How many sub-matrix are there in the matrix?
O($n^2$ * $n^2$) = O($n^4$)

解法1.Naive

计算矩阵和O($n^2$), 总Time:O($n^6$)

解法2.PreSum优化矩阵和计算

计算矩阵和O(1), 总Time:O($n^4$)
Space:O($n^2$)用来存左上角(0,0)->右下角(i,j)的矩阵和

class Solution(object): # TLE
    def maxSumSubmatrix(self, matrix, k):
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])

        # PreSum matrix
        dp = [[0] * (n+1) for _ in xrange(m+1)]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

        def sumRegion(row1, col1, row2, col2):
            return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1]

        res = -float('inf')
        for i in xrange(m):
            for j in xrange(n):
                for li in xrange(i, m):
                    for lj in xrange(j, n):
                        s = sumRegion(i, j, li, lj)
                        if s <= k:
                            res = max(res, s)
        return res

解法3.极其巧妙！

1 pre-processing 预处理 1D

从上到下做1D的preSum, O($n^2$)

2 任意取两行压缩成一个Array

瞬间把一个2D的matrix经过O($n^2$)转化成了1D的array

3 求一个Array里不大于k的连续subarray

新问题：求数组里不大于k的连续subarray O(nlogn)

TODO : python没有treeset的怎么搞？

560. Subarray Sum Equals K

Brute Force : $n^2$ subarray，Sum O($n$), Total O($n^3$)

Sol1. preSum

Improve Sum O($n^2$) to O(n)，but still O($n^2$), TLE

Sol2. HashTable, O(n)

A[0] + A[1] + … + A[j] = V

preSum[j] - preSum[i] = V similar to the Two Sum Problem，Query wether another part in preSum Array?

class Solution(object):
    def subarraySum(self, nums, k):
        preSum = defaultdict(int)
        s = count = 0
        preSum[0] = 1
        for n in nums:
            s += n
            if (s - k) in preSum:
                count += preSum[s - k]
            sums[s] += 1
        return count

325. Maximum Size Subarray Sum Equals k

longest subarray sum equals to k

preSum + HashTable

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        if not nums: return 0

        preSum = {}
        preSum[0] = -1
        s = res = 0
        for i, n in enumerate(nums):
            s += n
            pre = s - k
            if pre in preSum:
                res = max(res, i-preSum[pre])

            if s not in preSum:
                preSum[s] = i
        return res