Algorithm Tips 2: Dynamic programming in one article

Algorithm Tips 2: Dynamic programming in one article

This is the challenge I participated in more text on the 8th day, event details see: more text challenge

Recently, I want to sort out my own experience of brushing algorithm problems. On the one hand, for review and consolidation, on the other hand, I also hope that my sharing can help more friends who are learning algorithms.

The name of the column is "Algorithm Tips" . When explaining the algorithm, it will pay attention to the overall structure, but it will not cover everything. It is suitable for people with some algorithm experience.

This article talks about dynamic programming. All the topics and source code of this part are uploaded to the github directory , and the solution is mainly implemented in Python language.

Overview

If I were to use one sentence to describe the essence of the dynamic programming problem, it would be to find repetitive sub-problems.

In fact, divide-and-conquer recursive backtracking and dynamic programming have many commonalities, both of which are to find repetitive sub-problems, but they differ in specific implementation ideas. When there are more algorithms, you will find that any question can be used flexibly in any method, and a question can often be written in a variety of ways.

The most difficult part of dynamic programming is to find the DP equation. As long as you understand how to write the DP equation, you will be able to face a specific problem with ease.

Therefore, there is a situation for dynamic programming questions. People with ideas will quickly make them, and it is difficult for people without ideas. Therefore, it is difficult for this type of question to reflect the true level of the candidate in the algorithm interview, so the appearance rate It's not high.

Actual combat simulation

Next, I choose some typical example questions to explain, these questions basically cover all aspects of dynamic programming, from which you can get a glimpse of the whole picture of dynamic planning.

70. Climb stairs

The subject address is: leetcode-cn.com/problems/cl...

This is a very classic problem, which can be solved by recursion (pay attention to memorization), or iterative method, that is, dynamic programming.

The dp equation is:

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 code

53. Maximum Subsequence Sum

Subject address: leetcode-cn.com/problems/ma...

Given an integer array nums, find a continuous sub-array with the largest sum (the sub-array contains at least one element), and return its largest sum.

The dp equation is:

f(i)=max{f(i 1)+nums[i],nums[i]}

For each element, its maximum subsequence sum is either accumulated with the previous one, or independent of itself.

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 code

This question is a relatively simple type in dp. Just find a linear recursive relationship.

152. Maximum product sub-array

Subject address: leetcode-cn.com/problems/ma...

Given an integer array nums, please find the continuous sub-array with the largest product in the array (the sub-array contains at least one number), and return the product corresponding to the sub-array.

The difficulty of this question is that one dp equation cannot be satisfied and needs to be discussed in terms of positive and negative. Therefore, two dp 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 duplicated code

198. House Robbery

Subject address: leetcode-cn.com/problems/ho...

This question is a high-frequency question in interviews, and it is also a simple linear programming.

The solution I provided here does not use the dp array, which can save linear storage space.

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 secondCopy code

The upgraded version of the House Robber : 213. The House Robber II, address: leetcode-cn.com/problems/ho...

If the house is circular, the first place is removed, and the dynamic planning is performed 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 code

91. Decoding Method

Subject address: leetcode-cn.com/problems/de...

This question has a certain degree of difficulty, there are many cases to consider, and it is also a very classic dynamic programming question.

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 consecutive 0s appear if s[i- 1 ] + s[i] == "00" : return 0 # consider a single The letter if s[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 ] the else : return 0 return DP [- . 1 ] Copy the code

62. Different paths

Subject address: leetcode-cn.com/problems/un...

The one-dimensional dynamic programming was basically discussed above. In fact, the dp equation can also be two-dimensional, such as 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 code

There are many variations of this question.

  1. Different path 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): ifobstacleGrid[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
  1. Different path III leetcode-cn.com/problems/un...

Different path III uses the idea of backtracking, and there will be a special recursive topic to explain this kind of solution later.

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 and end er, ec = 0 , 0 step = 0 #The number of non-obstacles 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 if grid[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 and grid[nr][nc] !=- 1 : dfs_backtrace(nr, nc, step) grid[r][c] = 0 #Backtracking algorithm dfs_backtrace(sr, sc, step) return self.res Copy code

72. Edit distance

Subject address: leetcode-cn.com/problems/ed...

Let's finally look at this question, edit distance.

Given you two words word1 and word2, please calculate the minimum number of operands used to convert word1 to word2.

You can perform the following three operations on 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 (remove'r') rose -> ros (delete'e') Copy code

This question seems to have no idea, but in fact it is also a dynamic programming, and it needs to use 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 code