A preface.

I read a very good tweet before, and now I don’t know where it comes from, so I express this classic algorithm in easy to understand language.

Ii. Concept of Dynamic Programming Algorithm (WHAT)

(1) Definition.

Dynamic programming, a branch of operations research, is the process of solving the optimization of the decision process, and is widely used in algorithms to find the optimal solution (see Baidu Encyclopedia). My own understanding is that a big problem can be transformed into several small problems, and the solution of the small problem can be constructed, which is a bottom-up process. There is usually a cache array to cache the solution of the repeated subproblem and return the value whenever it is encountered in the future to improve the efficiency of the algorithm.

The process is usually as follows: first solve the smallest subproblem and store the results in a table. When solving the large subproblem, directly query the solution of the small subproblem from the table to avoid repeated calculation and thus improve the efficiency of the algorithm.

(2) and divide-and-conquer

Divide-and-conquer also divides the problem into subproblems; It combines the solutions of subproblems from the top down to obtain the solution of the original problem. The condition of dynamic programming is that there is an optimal substructure, and the optimal solution of the problem contains the optimal solution of its subproblem.

3. Why to Use and learn

Improve our algorithm to solve multiple complex mathematical problems; Such as Fibonacci problem, ladder problem, backpack problem, the most short circuit strength problem.

Iv. Usage Scenarios (WHERE)

All problems with optimal substructure can be solved by dynamic programming algorithm.

5. Common noun analysis

In general, when we use dynamic programming algorithms, we need to find the following “terms”

  1. State transition equation

Usually is the dynamic expression in which the left expression changes with the right expression. The statement is: F(n) = F(n-1) + F(n-2) (take the ladder problem as an example);

  1. Optimal substructure

Continue with the above example: the optimal substructure is the right formula F(n-1)+F(n-2).

  1. Boundary value

Continuing with the ladder problem, F(1) = 1 when n is 1 (only one walk), F(2) = 2(either one walk; Or divided into two times, a walk); The boundary values are F(1) and F(2).

6. Classic problem analysis.

1. Ladder problem

There was a staircase of ten steps, and you could only go up one or two steps for each step you took. How many ways are there to get to the top of the stairs?

Analysis of the: First we need to walk up to 10 steps: either you walk up to 8 or 9 steps,F(9),F(8); F(10)=F(9) +F(8), similarly F(9)=F(8)+F(7),F(8) =F(7)+F(6)… , the state transition equation can be obtained:F(n) = F(n-1) + F(n-1). What is the boundary value of this problem?? When n=3, F(3) = F(2) + F(1), F(2) represents step 2; There are only two ways to go, either one step, two steps in total; Either take two steps and do it all at once;The boundary values are F(1) and F(2), the process is shown in the figure:

Conclusion: This problem can be reformulated as a staircase with n steps in height. Go from the bottom to the top, and only one or two steps can be taken for each step. How many ways are there to get to the top of the stairs?

  • The state transition equation is: F(n) = F(n-1) + F(n-2)

  • The optimal substructure is: F(n-1)+ F(n-2)

  • The boundary values are: F(1) = 1 F(2) = 2

The final formula is as follows:

Now let’s look at the code

  1. The first way to write it.
#include "iostream"
using namespace std;

int getWay(int n) {
  if(n == 1) return 1;
  if(n == 2) return 2;
  return getWay(n- 1) + getWay(n2 -);
}

int main(a) {
  int n = 0;
  cout<<"Please enter the number of steps N"<<endl;
  cin >> n ;
  int result = getWay(n);
  cout<<"result is:"<<result<<endl;
  return 1;
} 
Copy the code

So if you’re a normal person and you write it the first way, you can easily see the double counting, F(8)=F(7)+F(6), F(7)=F(6)+F(5); The following is overwritten using a cache array:

#include "iostream"
#include <vector>
using namespace std;

// Cache array, element number 9999, initial market value 0
vector<int>Cache(9999.0); 
int getWay(int n) {
  if(n == 1) return 1;
  if(n == 2) return 2;
  // If the number is not in the cache array, cache it.
  if(Cache[n] == 0) {
      Cache[n] = getWay(n- 1) + getWay(n2 -);
  } 
  return Cache[n];
}
int main(a) {
  int n = 0;
  cout<<"Please enter the number of steps N"<<endl;
  cin >> n ;
  int result = getWay(n);
  cout<<"result is:"<<result<<endl;
  return 1;
} 
Copy the code

It’s easy to see that the time is O(n^2), and now let’s look at the more linear time order O(n).

  1. The second way to write it.
#include <iostream>
using namespace std;

/** * title: Now there are n stairs; A man has two ways; One step at a time; Or go up two steps at a time; How many ways are there for n steps? * F(N) = F(n-1) + F(n-2); * The optimal substructure is F(n-1) + F(n-2); * Its boundary values are: F(1) = 1 F(2) = 2(either once up the order (divided into two times up); Either take two steps at a time (one is required); * * * /

int getWays(int n) {
	if(n==1) return 1;
	if(n==2) return 2;
	int a=1, b=2;
	for(int i = 3; i<=n ; i++) {
		int temp = a + b;
		a = b;
		b = temp;
	}
	return b;
} 

int main(a) {
	int n = 0;
	cout<<"Please enter the number of steps N"<<endl;
	cin >> n ;
	int result = getWays(n);
	cout<<"result is:"<<result<<endl;
	return 1;
} 
Copy the code

The running results are as follows:

Write wrong place, welcome every big guy to put forward correction.

— For reference:

Baidu Encyclopedia dynamic planning

C + + vector analytical