1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        L1, L2 = len(text1), len(text2)
        dp = [[0] * (L1+1) for _ in range(L2+1)]

        for i in range(1, L2+1):
            for j in range(1, L1+1):
                if text2[i-1] == text1[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1]

1
2
3
4
5
6
7

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        for i in range(n-2, -1, -1):
            for j in range(len(triangle[i])):
                triangle[i][j] += min(triangle[i+1][j+1], triangle[i+1][j])
        return triangle[0][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [0] * N
        dp[0] = nums[0]
        for i in range(1, N):

            dp[i] = max(dp[i-1]+nums[i], nums[i])

        return max(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        N = len(nums)
        dp_max = [1] * (N)
        dp_min = [1] * (N)
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]

        for i in range(1, N):
            dp_max[i] = max(dp_max[i-1]*nums[i], nums[i], dp_min[i-1]*nums[i])
            dp_min[i] = min(dp_min[i-1]*nums[i], nums[i], dp_max[i-1]*nums[i])
        
        print(dp_max)
        print(dp_min)

        if max(dp_max) > max(dp_min):
            return  max(dp_max)
        else:
            return  max(dp_min)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
	def superEggDrop(self, K: int, N: int) -> int:
		cache = {}

		def dp(k,n):
			if k==1: return n
			if n==0: return 0

			if (k,n) in cache:
				return cache[(k,n)]

			# res = float('inf')
			# for x in range(1, n+1):
			# 	res = min(max(dp(k-1, x-1),dp(k, n-x))+1,res)

			res = float('inf')
			lo, hi = 1, n
			while lo <= hi:
				mid = (lo+hi) // 2

				broken = dp(k - 1, mid - 1)
				not_broken = dp(k, n - mid)
				
				if broken > not_broken:
					hi = mid - 1
					res = min(res, broken + 1)
				else:
					lo = mid + 1
					res = min(res, not_broken + 1)

			cache[(k,n)] = res

			return res

		return dp(K, N)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
	def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
		if not envelopes:
			return 0

		from functools import cmp_to_key
		def cmp(a, b):
			if a[0] == b[0]:
				return b[1] - a[1]
			else:
				return a[0] - b[0]

		tmp = sorted(envelopes, key=cmp_to_key(cmp))

		ll = [x[1] for x in tmp]

		dp = [1] * len(ll)

		for i in range(len(ll)):
			for j in range(i):
				if ll[i] > ll[j]:
					dp[i] = max(dp[i], dp[j]+1)

		return max(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
	def rob(self, nums: List[int]) -> int:
		if not nums:
			return 0
		if len(nums) == 1:
			return nums[0]

		N = len(nums)
		dp = [0] * N

		dp[0] = nums[0]
		dp[1] = max(nums[0], nums[1])

		for i in range(2, N):
			dp[i] = max(dp[i-1], dp[i-2] + nums[i])


		return max(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
	def rob(self, nums) -> int:
		if not nums:
			return 0
		if len(nums)==1:
			return nums[0]

		if len(nums)==2:
			return max(nums[0], nums[1])

		def fun(nums):
			N = len(nums)
			dp = [0] * N

			dp[0] = nums[0]
			dp[1] = max(nums[0], nums[1])

			for i in range(2, N):
				dp[i] = max(dp[i-1], dp[i-2] + nums[i])

			return max(dp)

		res1 = fun(nums[:-1])
		res2 = fun(nums[1:])
		return max(res1, res2)

 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 maxProfit(self, prices) -> int:
		if not prices:
			return 0
		cur_min = prices[0]
		max_res = 0
		for i in range(1, len(prices)):
			max_res = max(max_res, prices[i]-cur_min)
			cur_min = min(cur_min, prices[i])
		return max_res

# 1. 今天没有(昨天没有 保持不变，昨天有 卖了 )
# 2. 今天有(昨天没有 买，昨天有 保持不变)
class Solution:
	def maxProfit(self, prices) -> int:
		dp_0 = 0
		dp_1 = -float('inf')

		for p in prices:
			dp_0 = max(dp_0, dp_1 + p)
			dp_1 = max(dp_1, -p)
		return dp_0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
	def maxProfit(self, prices) -> int:
		if not prices:
			return 0
		dp_0 = 0
		dp_1 = -float('inf')

		res = 0

		for p in prices:
			tmp = dp_0
			dp_0 = max(dp_0, dp_1 + p)
			dp_1 = max(dp_1, tmp - p)
		return dp_0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxProfit(self, prices) -> int:
        if not prices:
            return 0
        
        dp_0, dp_1 = 0, -float('inf')
        pre_dp_0 = 0
        for p in prices:
            tmp = dp_0
            dp_0 = max(dp_0, dp_1 + p)
            dp_1 = max(dp_1, pre_dp_0 - p)
            pre_dp_0 = tmp
        return dp_0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxProfit(self, prices) -> int:
        dp_i10, dp_i20 = 0 ,0
        dp_i11, dp_i21 = -float('inf'), -float('inf')
        for p in prices:
            dp_i20 = max(dp_i20, dp_i21 + p)
            dp_i21 = max(dp_i21, dp_i10 - p)

            dp_i10 = max(dp_i10, dp_i11 + p)
            dp_i11 = max(dp_i11, -p);  # 第一次买
        return dp_i20

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
	def maxProfit(self, k: int, prices) -> int:
		if not prices or not k:
			return 0

		N = len(prices)

		if k > N / 2:
			dp_i_0, dp_i_1 = 0, -float('inf')
			for p in prices:
				tmp = dp_i_0
				dp_i_0 = max(dp_i_0, dp_i_1 + p)
				dp_i_1 = max(dp_i_1, tmp - p)
			return dp_i_0


		dp = [[ [0 for _ in range(2)] for _ in range(k+1) ] for _ in range(N)]

		for a in range(N): # 交易时间
			for b in range(k, 0, -1): # 交易次数
				if a == 0:
					dp[0][b][0] = 0
					dp[0][b][1] = -prices[a]
				else:
					dp[a][b][0] = max(dp[a-1][b][0], dp[a-1][b][1] + prices[a])
					dp[a][b][1] = max(dp[a-1][b][1], dp[a-1][b-1][0] - prices[a])

		return dp[N-1][k][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def maxProfit(self, prices, fee: int) -> int:
		if not prices:
			return 0

		dp_0 = 0
		dp_1 = -float('inf')
		for p in prices:
			dp_0 = max(dp_0, dp_1 + p - fee)
			dp_1 = max(dp_1, dp_0 - p)
		return dp_0