# 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

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

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

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

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

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

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

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```