动态规划高频题

「最优子结构」性质：原问题的解由子问题的最优解构成。

要符合「最优子结构」，子问题间必须互相独立。

5. 最长回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution

class Solution( ):
    def longestPalindrome(self, s):
        if not s: return s
        dp = [[False]*len(s) for _ in range(len(s))]
        res = s[0]
        
        for r in range(len(s)):
            for l in range(r):
                if l == r: dp[l][r] == True
                if r <= l+2: dp[l][r] = s[l]==s[r]
                if r > l + 2: dp[l][r] = s[l]==s[r] and dp[l+1][r-1]
                
                if dp[l][r] and r-l+1 > len(res):
                    res = s[l:r + 1]

        return res

300. 最长子序和

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Solution

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        
        dp = [1]*len(nums)
        
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1)
                    
        return max(dp)

To do: 动态规划 + 二分查找

322. 找零钱

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Solution

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        
        dp = [1]*len(nums)
        
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1)
                    
        return max(dp)

53. 最大子序和

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Solution

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

70. 爬楼梯

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2: return n
        
        dp = [0]*(n+1)
        dp[0], dp[1], dp[2] = 0, 1, 2
        
        for i in range(3, n+1):
            dp[i] = dp[i-2] + dp[i-1]
            
        return dp[-1]

121. 买卖股票的最佳时机

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        
        dp = [0]*len(prices)
        min_v = prices[0]
        
        for i in range(1, len(prices)):
            min_v = min(min_v, prices[i])
            dp[i] = prices[i] - min_v
            
        return max(dp)

91. 解码方法

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Solution

除了太多错。。。

279. 完全平方数

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution

超时...

class Solution:
    def numSquares(self, n: int) -> int:
        
        dp = [i for i in range(n+1)]
        csquares = [0]
        for i in range(1, int(n**0.5)+1):
            csquares.append(i*i)
            
        for i in range(1, n+1):
            for c in csquares:
                if i-c>=0:
                    dp[i] = min(dp[i-c]+1, dp[i])
                    
        return dp[-1]

152. 最大乘积子序列

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solution

自己解的，但可以再熟悉一下...

class Solution:
    def maxProduct(self, nums) -> int:
        if not nums: return 0
        
        dp = [[1,1] for _ in nums]
        dp[0] = [nums[0], nums[0]]
        
        for i in range(1, len(nums)):
            if nums[i]>0: 
                dp[i][0] = min(nums[i], dp[i-1][0]*nums[i])
                dp[i][1] = max(nums[i], dp[i-1][1]*nums[i])
            
            else:
                dp[i][0] = min(nums[i], dp[i-1][1]*nums[i])
                dp[i][1] = max(nums[i], dp[i-1][0]*nums[i])
        
        return max(dp, key=lambda x:x[1])[1]

139. 单词拆分

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Solution

没想到and dp[l]

class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        if not s: return False
        dp = [True] + [False]*len(s)
        
        for l in range(len(s)):
            for r in range(l+1, len(s)+1):
                if s[l:r] in wordDict and dp[l]:
                    dp[r] = True
                    
        return dp[-1]

62. 不同路径

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Solution

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m==0 or n==0: return 0
        if m==1 or n==1: return 1
        
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        
        dp[1][2] = dp[2][1] = 1
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if dp[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1] 
                    
        return dp[m][n]

198. 打家劫舍

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Solution

class Solution:
    def rob(self, nums) -> int:
        if len(nums)==0: return 0
        if len(nums)==1: return nums[0]
        
        dp = [0] * len(nums)
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
            
        return dp[-1]