动态规划高频题
原创
「最优子结构」性质：原问题的解由子问题的最优解构成。
要符合「最优子结构」，子问题间必须互相独立。
数学系列
300. 最长上升子序列
从最长递增子序列学会如何推状态转移方程 link
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: 动态规划 + 二分查找
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)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]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]其他
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 stepsExample 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 stepSolution
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]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]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?
Above is a 7 x 3 grid. 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 -> RightExample 2:
Input: m = 7, n = 3
Output: 28Solution
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]原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。