Leetcode dynamic programming

Posted on | Post modified

53. Maximum Subarray

dp[i] means if the the maximum subarray that contains the ith element.

1
2
3
4
5
6
7
8
9
10
11
12
13
def maximum_subarray(x):
    if len(x)==0:
        return None
    dp=[float('-inf')]*len(x)
    res=x[0]
    dp[0]=x[0]
    for i in range(1,len(x)):
        dp[i]=max(x[i],dp[i-1]+x[i])
        
    return max(dp)

a=[-2,1,-3,4,-1,2,1,-5,4]
print(maximum_subarray(a))
1
2
3
4
5
6
7
8
9
10
11
12
13
def maximum_subarray(x):
    if len(x)==0:
        return None
    dp=[float('-inf')]*len(x)
    res=x[0]
    dp[0]=x[0]
    for i in range(1,len(x)):
        dp[i]=max(x[i],dp[i-1]+x[i])
        res=max(res,dp[i])
    return res

a=[-2,1,-3,4,-1,2,1,-5,4]
maximum_subarray(a)
6

300. Longest Increasing Subsequence

这里dp[i]的含义是x[i]在subset中，且是subset中最后一个元素的情况下，最大长度是多少。

1
2
3
4
5
6
7
8
9
10
11
def longest_increasing_subsequence(x):
    if len(x)==0:
        return None
    dp=[1]*len(x)
    for i in range(len(x)):
        for j in range(i):
            if x[j]<x[i]:
                dp[i]=max(dp[i],dp[j]+1)
    return max(dp)
a= [10,9,2,5,3,7,101,18]
longest_increasing_subsequence(a)
4

139.Word Break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return False
        # dp保存dp【i】i之前的最少字符串
        dp = [False] * (len(s) + 1)
        dp[0] = True
        # 本身的循环，对字符串，在内层循环中需要使用i
        for i in range(1, len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True # 因为j～i是一个回文字符串
        return dp[-1]

198. House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 def house_robber(x):
    if len(x)==0:
        return 0
    if len(x)==1:
        return x[0]
    dp=[0]*len(x)
    dp[0]=x[0]
    dp[1]=max(x[0],x[1])
    for i in range(2,len(dp)):
        dp[i]=max(dp[i-1],dp[i-2]+x[i])
    return dp[-1]

a=[1,2,3,1]
house_robber(a)
4

303. Range Sum Query - Immutable

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 NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        total = 0
        self.dp = []    
        for i in nums:
            total += i
            self.dp.append(total)


    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.dp[j]
        return self.dp[j] - self.dp[i-1]



# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

368. Largest Divisible Subset

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 largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        nums = sorted(nums)
        size = len(nums)
        dp = [1] * size
        pre = [None] * size
        for x in range(size):
            for y in range(x):
                if nums[x] % nums[y] == 0 and dp[y] + 1 > dp[x]:
                    dp[x] = dp[y] + 1
                    pre[x] = y
        idx = dp.index(max(dp))
        ans = []
        while idx is not None:
            ans += nums[idx],
            idx = pre[idx]
        return ans

338. Counting Bits

需要熟悉Bit运算和概念，要能发现countbit(n) = countbit(n/2) + n % 2这么一个方程，就是说一个数乘2意味着bit位左移一位

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0 for _ in range(num+1)]
        for i in range(num+1):
            dp[i] = dp[i>>1] + i%2
        return dp

264. Ugly Number II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def nthUglyNumber(n):
    """
    :type n: int
    :rtype: int
    """
    ugly = [1]
    i2, i3, i5 = 0, 0, 0
    for i in range(n-1):
        u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
        #print(u3)

        umin = min(u2, u3, u5)
        if umin == u2:
            i2 += 1
        if umin == u3:
            i3 += 1
        if umin == u5:
            i5 += 1
        ugly.append(umin)
        print(ugly)
    return ugly[-1]
nthUglyNumber(10)
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 8]
[1, 2, 3, 4, 5, 6, 8, 9]
[1, 2, 3, 4, 5, 6, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]





12

673. Number of Longest Increasing Subsequence

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
36
def dp(x):
    dp=[1]*len(x)
    Count=[1]*len(x)
    for i in range(1,len(x)):
        temp=[1]
        y=[1]
        for j in range(i):
            if x[j]<x[i]:
                temp.append(dp[j]+1)
                y.append(Count[j])
        print(temp)
        tempMax=max(temp)
        count=0
        for k in range(len(temp)):
            if temp[k]==tempMax:
                count+=y[k]
        Count[i]=count
        dp[i]=tempMax
    print(Count)
    print(dp)
    tempMax=max(dp)
    ans=[]
    count=0

    for i in range(len(dp)):
        if dp[i]==tempMax:
            ans.append(i)
    res=0
    for j in ans:
        res+=Count[j]
    return res
a=[2,2,2,2]
print(dp(a))
a= [1,3,5,4,7]
a=[1,2,4,3,5,4,7,2]
print(dp(a))
[1]
[1]
[1]
[1, 1, 1, 1]
[1, 1, 1, 1]
4
[1, 2]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3, 4, 4]
[1, 2, 3, 4]
[1, 2, 3, 4, 4, 5, 5]
[1, 2]
[1, 1, 1, 1, 2, 1, 3, 1]
[1, 2, 3, 3, 4, 4, 5, 2]
3

1
2
a=[1,2,1]
a.count(1)
2