Dynamic Programming

1 Best Time to Buy and Sell Stock

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0

        low = prices[0]
        res = 0
        for p in prices:
            res = max(res, p - low)
            low = min(p, low)
        return res

2 Decode Ways

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        dp = [0]*len(s) + [1]
        for i in range(len(s)):
            if s[i] != '0':
                dp[i] = dp[i-1]
                if i >= 1 and 10 < int(s[i-1:i+1]) <= 26:
                    dp[i] += dp[i-2]
            else:
                if i == 0 or (int(s[i-1]) < 1 or int(s[i-1]) > 2):
                    return 0
                else:
                    dp[i] += dp[i-2]

        return dp[-2]

3 Minimum Window Subsequence

这道题主要思想dp[i][j]代表。如果要能匹配到T中的第i位，到S中第j位字符串长度为多少。

[[0, 1, 2, 3, 4, 1, 2, 3, 4],
 [0, 0, 0, 3, 4, 5, 2, 3, 4],
 [0, 0, 0, 0, 4, 5, 6, 7, 4]]

class Solution(object):
    def minWindow(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: str
        """
        dp = [[0]*len(S) + [0] for _ in range(len(T))]
        index, length = 0, 1<<31
        for i in range(len(T)):
            for j in range(len(S)):
                if S[j] == T[i] and (i==0 or dp[i-1][j-1]):
                    dp[i][j] = dp[i-1][j-1] + 1
                    if i == len(T)-1 and dp[i][j]<length:
                            index, length = j, dp[i][j]
                elif dp[i][j-1]>0:
                    dp[i][j] = dp[i][j-1] + 1

        if length!=1<<31:
            return S[index-length+1: index+1]
        else:
            return ""

s = Solution()
print s.minWindow("abcdebdde",  "bde")

4 Maximum Sum of 3 Non-Overlapping Subarrays

抄一个大佬的。实在没法比他写得好。呜呜呜

class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        # Best single, double, and triple sequence found so far
        bestSeq = 0
        bestTwoSeq = [0, k]
        bestThreeSeq = [0, k, k*2]

        # Sums of each window
        seqSum = sum(nums[0:k])
        seqTwoSum = sum(nums[k:k*2])
        seqThreeSum = sum(nums[k*2:k*3])

        # Sums of combined best windows
        bestSeqSum = seqSum
        bestTwoSum = seqSum + seqTwoSum
        bestThreeSum = seqSum + seqTwoSum + seqThreeSum

        # Current window positions
        seqIndex = 1
        twoSeqIndex = k + 1
        threeSeqIndex = k*2 + 1
        while threeSeqIndex <= len(nums) - k:
            # Update the three sliding windows
            seqSum = seqSum - nums[seqIndex - 1] + nums[seqIndex + k - 1]
            seqTwoSum = seqTwoSum - nums[twoSeqIndex - 1] + nums[twoSeqIndex + k - 1]
            seqThreeSum = seqThreeSum - nums[threeSeqIndex - 1] + nums[threeSeqIndex + k - 1]

            # Update best single window
            if seqSum > bestSeqSum:
                bestSeq = seqIndex
                bestSeqSum = seqSum

            # Update best two windows
            if seqTwoSum + bestSeqSum > bestTwoSum:
                bestTwoSeq = [bestSeq, twoSeqIndex]
                bestTwoSum = seqTwoSum + bestSeqSum

            # Update best three windows
            if seqThreeSum + bestTwoSum > bestThreeSum:
                bestThreeSeq = bestTwoSeq + [threeSeqIndex]
                bestThreeSum = seqThreeSum + bestTwoSum

            # Update the current positions
            seqIndex += 1
            twoSeqIndex += 1
            threeSeqIndex += 1

        return bestThreeSeq