Algorithm Interview Replay: Taking the Stairs (bytes)

01. Concept explanation

There is a lot of information about dynamic programming. The official definition is to convert a multi-stage process into a series of single-stage problems, and solve them one by one using the relationship between the stages. The relationship between the stages in the concept is actually referred to as the state transition equation. Many people find DP difficult (hereinafter referred to as DYNAMIC programming DP). The fundamental reason is that DP is different from some algorithms with fixed forms (such as DFS, dichotomy and KMP). It has no actual steps to specify what the first and second steps should do.

The essence of this idea is: a big problem (which can be expressed in two or three parameters of the problem), can be the result of a number of smaller problems to get (usually seek to the calculation of some special logic, such as get the most value, etc.), as shown in the figure below, a large-scale problem is composed of several sub problems.

So how do we get large-scale problems from subproblems? This is the use of the transition equation, we usually see the state transition equation, basically like this:

Opt: indicates a special calculation logic, usually Max or min. I,j,k are all parameters that are used in defining the DP equation. dp[i] = opt(dp[i-1])+1 dp[i][j] = w(i,j,k) + opt(dp[i-1][k]) dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)Copy the code

Each of these state transition equations, there are more or less subtle differences. This is actually very easy to understand, there are so many relations in the world, it is impossible to abstract out a completely applicable formula. So I personally don’t recommend memorizing various types of state transition equations. But is it true that the question type of DP is completely impossible to grasp and classify for analysis? I don’t think so. In this series, I’ll cover the topic of dynamic programming in a nutshell.

02. Topic analysis

Let’s look at one of the simplest DP problems to familiarize ourselves with the concept of DP:

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

03. Graphical analysis

Through analysis, we can make it clear that the problem can be decomposed into some subproblems containing optimal substructure, that is, its optimal solution can be effectively constructed from the optimal solution of the subproblem. The condition of “splitting a big problem into several smaller problems” is satisfied. So let dp[n] represent the total number of methods that can reach the NTH order, and the following state transition equation can be obtained:

dp[n]=dp[n-1]+dp[n-2]

• Go up one step: There is one way.

• Go up 2 steps: there are 1+1 and 2 ways.

• Up 3 steps: The total number of ways to reach level 3 is the sum of the ways to reach level 1 and level 2.

• So the total number of ways to get to order n is the sum of the ways to get to order N minus 1 and order N minus 2.

04. Examples of GO language

According to the above analysis, the code can be obtained as follows:

func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i- 1] + dp[i2 -]}return dp[n]
}
Copy the code

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download