This is the 13th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Dynamic programming algorithm

The general form of dynamic programming problem is to find the maximum value:
- Dynamic programming is an optimization method in operations research
Application scenarios of dynamic programming:
- Find the longest increasing subsequence
- Find the minimum edit distance
Core problems of dynamic programming:
- Brute force
- Because to get the best value, you have to exhaust all the possible answers and then find the best value
The exhaustiveness of dynamic programming is special:
- There are overlapping subproblems:
  - If brute force is inefficient
  - You need to use a memo or DP Table to optimize the exhaustive process and avoid unnecessary calculations
- Optimal substructure: in this way, the best value of the original problem can be found by the best value of the subproblem
- Listing the right state transition equations is the only way to exhaustive correctly: it is not easy to enumerate all possible solutions
Three elements of dynamic programming:
- Overlapping subproblem
- Optimal substructure
- State transition equation
Thinking framework of state transition equation:
- Clearly state
- Defines the meaning of a DP array or function
- A clear choice
- Clear the base case

Fibonacci series

Direct recursion

The mathematical form of the Fibonacci sequence is recursive. The code is as follows:

int fib(int N) {
	if (N == 1 || N == 2) {
		return 1;
	} 
	return fib(N- 1) + fib(N2 -);
}
Copy the code

This is the easiest way to do direct recursion, and it’s also the least efficient way to do it, as you can see by drawing the recursion tree

Recursion problem analysis, it is best to draw the recursion tree, easy to analyze the complexity of the algorithm, to find the reason for the inefficient algorithm
The time complexity of a recursive algorithm is equal to the number of subproblems * the time it takes to solve a subproblem

When N=20, Fibonacci sequence recursion tree analysis:

To compute f(20), you have to compute f(19) and f(18), and then to compute f(19), you have to compute f(18) and f(17), and so on. And then when we get to f(2) and f(1), we know. And then the recursion tree ends

According to the recursive algorithm, the time complexity is equal to the number of subproblems times the time required to solve a subproblem:

Number of subproblems: the total number of nodes in the recursion tree. Because the total number of nodes in a binary tree is exponential, the number of all subproblems is O(2^N^).

Time required to solve a subproblem: since there is no loop in this algorithm, only f(n-1)+f(n-2) an addition operation, all time is O(1).

The time complexity of the direct recursive algorithm is O(2^n^), which is an exponential level. Is quite complicated

Observe the recursion tree and analyze the reasons for the low efficiency of the algorithm:

There’s a lot of double counting

F (18) has been calculated twice, and the recursion tree with f(18) as its root is huge, so it takes a lot of time to do it again

Moreover, not only the node f(18) will be double-counted, resulting in low algorithm

This problem is the first property of dynamic programming: overlapping subproblems

Recursive algorithm with memo

Overlapping subproblem solved:
- The reason it takes time is because of double counting
- So you can create oneMemo:
  - Each time you work out an answer to a subproblem, you record it in a memo and return it
  - Every time you encounter a subproblem, go to the memo first
  - If you find the solved problem in the memo, just get the answer. No more computations
It’s common to use an array as a memo, but you can also use a Hash table as a memo:

int fib(int N) {
	if (N < 1) {
		return 0;
	}
	// The memo is initialized to 0
	vector<int> memo(N+1.0);
	// Initialize the simplest case
	return helper(memo, N);	
}

int helper(vector<int>& memo, int n) {
	if (n == 1 || n == 2) {
		return 1;
	}
	// Return the computed ones directly
	if(memo[n] ! =0) {
		return memo[n];
	}
	memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
	return memo[n];
}
Copy the code

Recursive tree analysis of recursive algorithm with memo:

The algorithm of recursion tree with memo is to transform a recursion tree with huge redundancy into a recursion graph without redundancy by pruning, which greatly reduces the subproblem, that is, the number of nodes in the recursion tree

According to the recursive algorithm, the time complexity is equal to the number of subproblems times the time required to solve a subproblem:

Number of subproblems: the total number of nodes in the recursion tree. Since there is no redundant computation, the subproblem is f(1),f(2)… F (20) is proportional to the size n of the input, so the number of subproblems is O(n).

Time to solve a subproblem: since there are no loops in this algorithm, only addition operations, the time is O(1).

Recursive algorithm with memo time complexity: O(n). Much more efficient than direct recursive algorithm

The recursive solution with memorandum is as efficient as the iterative dynamic programming solution:
- Recursive solution with memo:The top-down
  - It goes from top to bottom
  - From a large source problem, the problem size is gradually broken down until the bottom is reached. Then return the answer one level at a time
- Iterative dynamic programming solution:From the bottom up
  - Start directly at the bottom of the smallest problem and work your way up until you derive the answer you need. That’s the idea of dynamic programming
  - Dynamic programming generally breaks away from recursion and uses cyclic iteration to complete the calculation

DP array iteration algorithm

On the basis of the memo, the memo is independent into a Table, called DP Table
Complete bottom-up calculation on DP Table:

int fib(int N) {
	vector<int> dp(N+1.0);
	dp[1] = dp[2] = 1;
	for (int i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[N];
}
Copy the code

The structure of the DP Table is very similar to the pruned recursive tree of the memo, but it is calculated in reverse. In fact, the memo in the recursive solution with the memo ends up with this DP Table. So the recursive algorithm with the memo and the iterative algorithm with the DP array are just as efficient in most cases

State transition equation:A mathematical form that describes the structure of a problem
- State transition: For example, if you want to make f(n) into a state n, the state N is transferred by adding the states n-1 and n-2
- State escape equation is the core of solving the problem
- The state transition equation directly represents the violent solution
The most difficult part of dynamic programming is to write the state transition equation

Fibonacci number solution supplement

According to the Fibonacci sequence state transition equation:
- The current state is only related to the previous two states
- So you don’t need a long DP Table to store all the states
- Just store the two states between them
- You can optimize the space complexity to O(1)

int fib(int n) {
	if (n == 1 || n ==2) {
		return 1;
	}
	int prev = 1, curr = 1;
	for (int i = 3; i <= n; i++) {
		int sum = prev + curr;
		prev = curr;
		curr = sum;
	}
	return curr;
}
Copy the code

Change problem

Topic:
- For k coins of denominations c1, C2,… Ck. Each coin has an infinite number of coins, and the total amount needs to be reached. It takes at least a few coins to reach the amount, if not, return -1
For a computer, the way to solve this problem is to enumerate all the possible ways to gather coins and find the minimum number of coins needed

Direct recursion

To conform to the optimal substructure, subproblems must be independent of each other
Analysis of the change problem:
- This problem is a dynamic programming problem because it hasOptimal substructure
  - Original problem: let’s ask for the minimum number of coins when amount=11
  - Subproblem: if you know the minimum number of coins to raise amount=10
  - Just add 1 to the answer to the subquestion. Choose another coin of 1 to get the answer to the original question
  - Because there’s no limit to the number of coins, there’s no limit to the number of subproblems, they’re independent of each other
= =After it is determined to be a dynamic programming problem, it is necessary to think about how to list the state transition equation:= =
- First determine the status:
  - The state is the number of changes in the original problem and the subproblem
  - Since the number of coins is infinite, the only state is the target amount
- Then define the DP function:
  - The current target amount is N, and at least DP (n) coins are needed to make up that amount
- Then determine the choice and choose the best:
  - So for each state, what choices can I make to change the current state
  - Regardless of the current target amount, the choice is to select a coin from the denomination list Coins, and then the target amount is reduced
  - The pseudo-code is as follows:
```
 def coinChange(coins: List[int], amount: int) :
 	# Definition: It takes at least DP (n) coins to make up the sum n
 	def dep(n) :
 		Choose: Choose the result that requires the fewest coins
 		for coin in coins:
 			res = min(res, 1 + dp(n - coin))
 		return res;
 	# Calculate the required problem dp(amount)
 	return dp(amount)
Copy the code
```
- Base case:
  - Specify the initial known state
  - When the target amount is 0, the number of coins required is 0. When the target amount is less than 0, there is no solution. Return 1

def coinChange(coins: List[int], amount: int) :
	def dp(n) :
		if n==0: return 0
		if n < 0: return -1
		# minimizes, so initializes to infinity
		res = float('INF')
		for coin in coins:
			subproblem = dp(n - coins)
			if subproblem == -1: continue
			res = min(res, 1 + subproblem)
		return res ifres ! =float('INF') else -1
	return dp(amount);
Copy the code

The mathematical form of the above code is the state transition equation obtained by direct recursion
To eliminate overlapping subproblems:
- Recursive tree analysis of direct recursive algorithm:
  - Based on the time complexity equal to the total number of subproblems times the time of each subproblem:
    - Total number of subproblems: It is difficult to see the specific number of subproblems of this problem, which can be analyzed as O(n^k^), which is the number of exponential level
    - Time per subproblem: Each subproblem contains a for loop, so the time complexity is O(k).
    - Algorithm time complexity: O(k * n^k^). Is an exponential level

Recursive algorithm with memo

Overlapping subproblems can be eliminated with a memo:

def coinChanges(coins: List[int], amount: int) :
	# memo
	memo = dict(a)def dp(n) :
		# Check the memo to avoid double counting
		if n in memo: return memo[n]
		If it does not exist in the memo, the calculation is performed
		if n = 0: return 0
		if n < 0: return -1
		# minimizes, so initializes to infinity
		res = float('INF')
		for coin in coins:
			subproblem = dep(n - coin)
			if subproblem == -1: continue
			res = min(res, 1 + subproblem)
		Enter the calculation results in the memo
		memo[n] = res ifres ! =float('INF') else -1
		return memo[n]
	return dep(amount) 
Copy the code

Recursive tree analysis of recursive algorithm with memo:
- According to the algorithm the time complexity is equal to the total number of subproblems times the time of each subproblem
  - Total number of subproblems: Due to the reference to the memorandum, the number of subproblems is greatly reduced and the redundancy of subproblems is completely eliminated, so that the total number of subproblems does not exceed N, i.e. the number of subproblems is O(n).
  - Time per subproblem: Processing time per subproblem is O(k) due to the for loop.
  - The time complexity of the algorithm is O(kn), which greatly improves the efficiency of the algorithm

DP array iteration algorithm

Use DP Table bottom-up to eliminate overlapping subproblems

int coinChanges(vector<int> coins, int amount) {
	// The array size is amount+1, and the initial value is also amount+1
	vector<int> dp(amount + 1, amount + 1);
	/* * dp[I] = x: * When the target amount is I, at least x coins are required */
	 for (int i = 0; i < dp.size(); i++) {
	 	// The inner layer for is to minimize all subproblems +1
	 	for (coin in coin) {
	 		// If the subproblem has no solution, skip the loop
	 		if (i - coin < 0) {
	 			continue;
	 		}
	 		dp[i] = min(dp[i], 1 + dp[i - coin])
	 	}
	 }
	 return (dp[amount] == dp[amount + 1])?- 1 : dp[amount];
}
Copy the code

The array is initialized to amount+1 because the number of coins that add up to amount can only be equal to amount if all of them are $1 coins
Initializing amount+1 is the same thing as initializing it to infinity so that it can be minimized

conclusion

Fibonacci question:
- How to optimize a recursion tree using a memo or DP Table
- It is clear that the two approaches are essentially the same, with the difference between top down (memo) and bottom up (DP Table)
Change problem:
- Show how to process to determine the state transition equation
- Just write the algorithm for direct recursion through the state escape equation, and then you can eliminate overlapping subproblems by optimizing the recursion tree
The only way for a computer to solve a problem is to exhaust:
- Exhaust all the possibilities
- Algorithmic design is about thinking how do you exhaust
- And then we look for ways to optimize the exhaustive
How to exhaustive:The dynamic transfer equation is listed
- Listing the dynamic transfer equation is solving the problem of how to exhaustive. Listing the dynamic transfer equation is difficult because:
- A lot of exhaustion needs to be implemented recursively
- The solution space of some problems is complex and not easy to complete
Ways to optimize exhaustion:Memorandum and DP Table
- Memos and DP Tables are ways to optimize the exhaustive
- The idea is to use space for time to reduce the time complexity of the algorithm

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Algorithm learning path: The easiest way to tell you about dynamic programming algorithms

Dynamic programming algorithm

Fibonacci series

Direct recursion

Recursive algorithm with memo

DP array iteration algorithm

Fibonacci number solution supplement

Change problem

Direct recursion

Recursive algorithm with memo

DP array iteration algorithm

conclusion

Algorithm learning path: The easiest way to tell you about dynamic programming algorithms

Dynamic programming algorithm

Fibonacci series

Direct recursion

Recursive algorithm with memo

DP array iteration algorithm

Fibonacci number solution supplement

Change problem

Direct recursion

Recursive algorithm with memo

DP array iteration algorithm

conclusion

Related Posts

【 summary 2020】 The most realistic Java post interview questions (Baidu, 360, Tencent real questions)

Summary and comprehension about the AVL tree | in 19 days

Python multiple inheritance with super