This is the 8th day of my participation in Gwen Challenge
Recently, I want to sort out my experience of brush algorithm. On the one hand, I want to review and consolidate. On the other hand, I also hope that my sharing can help more friends in learning algorithm.
The column is called “Algorithm Tips”, which will focus on the overall structure of the algorithm, but will not cover all aspects. It is suitable for those who have some algorithm experience to read.
This article is about dynamic programming. All the questions and source code of this part are uploaded to github. The solution is mainly implemented in Python.
An overview of the
If I had to describe the essence of dynamic programming problems in one sentence, it would be to find repeating subproblems.
In fact, divide-and-conquer recursive backtracking and dynamic programming have a lot in common, both are to find repeating subproblems, but there are differences in the specific implementation ideas. Wait until the algorithm to do more will find that which problem should use what method can be flexibly used, and a problem can often use a variety of writing methods to do.
The hardest part of dynamic programming is finding the DP equation. Once you know how to write the DP equation, you’ll be able to handle a particular problem with ease.
Therefore, there is a situation of dynamic planning questions, people with ideas will soon do it, people without ideas will be difficult to do it, so this kind of questions in the algorithm interview is difficult to reflect the real level of candidates, so the appearance rate is not high.
Actual combat simulation
Next, I choose some typical examples to explain, these topics basically cover all aspects of dynamic programming, you can see the full picture of dynamic programming.
70. Climb the stairs
The subject address is leetcode-cn.com/problems/cl…
This is a very classic problem, and you can do it recursively (remember), or you can do it iteratively, or dynamically.
Dp equation: f(x)= F (x−1)+f(x−2)
class Solution:
def climbStairs(self, n: int) - >int:
a, b = 1.1
for _ in range(n):
a, b = b, a+b
return a
Copy the code53. Maximum suborder sum
Subject address: leetcode-cn.com/problems/ma…
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
F (I)= Max {f(I −1)+nums[I],nums[I]}
For each element, its maximum suborder sum either adds up to the previous one or it’s independent.
class Solution:
def maxSubArray(self, nums: List[int]) - >int:
for i in range(1.len(nums)):
nums[i] = max(nums[i], nums[i]+nums[i-1])
return max(nums)
Copy the codeThis problem is the simpler type of dp, just find a linear recursive relationship
152. Maximum subarray of product
Subject address: leetcode-cn.com/problems/ma…
Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.
The difficulty of this problem is that one DP equation cannot be satisfied, so it needs to be discussed in terms of positive and negative, so two DPS are used to solve the problem.
class Solution:
def maxProduct(self, nums: List[int]) - >int:
mi = ma = res = nums[0]
for i in range(1.len(nums)):
if nums[i] < 0: mi, ma = ma, mi
ma = max(ma * nums[i], nums[i])
mi = min(mi * nums[i], nums[i])
res = max(res, ma)
return res
Copy the code198. Robbery
Subject address: leetcode-cn.com/problems/ho…
This is a frequent interview question, and it’s a simple linear program.
The solution I present here does not use dp arrays and saves linear storage.
class Solution:
def rob(self, nums: List[int]) - >int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
first, second = nums[0].max(nums[0], nums[1])
for i in range(2, size):
first, second = second, max(first + nums[i], second)
return second
Copy the code213. raid HOUSE II, address: leetcode-cn.com/problems/ho…
If the house is circular, remove the first place respectively and make dynamic planning twice.
class Solution:
def rob(self, nums: List[int]) - >int:
def my_rob(nums) :
cur, pre = 0.0
for num in nums:
cur, pre = max(pre + num, cur), cur
return cur
return max(my_rob(nums[:-1]),my_rob(nums[1:))if len(nums) ! =1 else nums[0]
Copy the code91. Decoding method
Subject address: leetcode-cn.com/problems/de…
This problem has a certain degree of difficulty, need to consider a lot of cases, is also a very classic dynamic programming problem.
class Solution:
def numDecodings(self, s: str) - >int:
dp = [0] * len(s)
# Consider the first letter
if s[0] = ="0":
return 0
else:
dp[0] = 1
if len(s) == 1: return dp[-1]
# Consider the second letter
if s[1] != "0":
dp[1] + =1
if 10< =int(s[:2< =])26:
dp[1] + =1
for i in range(2.len(s)):
# when two zeros appear in a row
if s[i - 1] + s[i] == "00": return 0
# Consider a single letter
ifs[i] ! ="0":
dp[i] += dp[i - 1]
if 10< =int(s[i - 1] + s[i]) <= 26:
dp[i] += dp[i - 2]
# Consider two letters
else:
if 1< =int(s[i-1< =])2:
dp[i] += dp[i - 2]
else:
return 0
return dp[-1]
Copy the code62. Different paths
Subject address: leetcode-cn.com/problems/un…
We’ve talked about dynamic programming in one dimension, but dp equations can also be two-dimensional, as in this very classic series of different paths.
class Solution:
def uniquePaths(self, m: int, n: int) - >int:
dp = [[1] * m]
for _ in range(n-1):
dp.append([1] + [0] * (m-1))
for i in range(1, m):
for j in range(1, n):
dp[j][i] = dp[j-1][i] + dp[j][i-1]
return dp[-1] [-1]
Copy the codeThere are many variations on this problem.
- Different paths II leetcode-cn.com/problems/un…
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - >int:
n = len(obstacleGrid)
if not n: return 0
m = len(obstacleGrid[0])
if not m: return 0
dp = [[0]*m for _ in range(n)]
for i in range(0, m):
if obstacleGrid[0][i] == 1: break
dp[0][i] = 1
for j in range(0, n):
if obstacleGrid[j][0] = =1: break
dp[j][0] = 1
for i in range(1, n):
for j in range(1, m):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1] [-1]
Copy the code- Different paths III leetcode-cn.com/problems/un…
Different paths III uses the idea of backtracking, and there will be a special section on recursion on this kind of solution.
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) - >int:
R, C = len(grid), len(grid[0])
self.res = 0
sr, sc = 0.0 # start end
er, ec = 0.0
step = 0 # Number of non-barriers
for r in range(R):
for c in range(C):
if grid[r][c] == 1: sr, sc = r, c
if grid[r][c] == 2: er, ec = r, c
ifgrid[r][c] ! = -1: step += 1
def dfs_backtrace(r, c, step) :
step -= 1
if r == er and c == ec:
if step == 0:
self.res += 1
return
grid[r][c] = -1
for nr,nc in ((r-1,c),(r,c+1),(r+1,c),(r,c-1)) :if 0<=nr<R and 0<=nc<C andgrid[nr][nc] ! = -1:
dfs_backtrace(nr, nc, step)
grid[r][c] = 0 # backtracking algorithm
dfs_backtrace(sr, sc, step)
return self.res
Copy the code72. Edit distance
Subject address: leetcode-cn.com/problems/ed…
Let’s finish with this one, edit distance.
Given two words word1 and word2, please calculate the minimum operand needed to convert word1 into word2.
You can do one of three things with a word:
Insert a character, delete a character, replace a character
Example:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (delete 'r') rose -> ros (delete 'e')Copy the codeThis seems like a crazy problem, but it’s also dynamic programming, and it’s using a two-dimensional matrix.
class Solution:
def minDistance(self, word1: str, word2: str) - >int:
row, col = len(word1)+1.len(word2)+1
dp = [[0] * col for _ in range(row)]
for i in range(0, row):
dp[i][0] = i
for j in range(0, col):
dp[0][j] = j
for i in range(1, row):
for j in range(1, col):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
return dp[-1] [-1]
Copy the code