Algorithm is introduced into

Dynamic Programming (DP for short) is a method used in mathematics, management science, computer science, economics and bioinformatics to solve complex problems by decomposing the original problem into relatively simple sub-problems.


Dynamic programming is often applied to problems with overlapping subproblems and optimal substructure, and the time of dynamic programming is often much less than that of the naive method.


The basic idea behind dynamic programming is simple. Roughly speaking, to solve a given problem, we need to solve its different parts (i.e., subproblems), and then use the solutions of the subproblems to arrive at the solution of the original problem. Dynamic programming is often used to optimize recursive problems, such as Fibonacci sequence. If a recursive method is used to solve many of the same subproblems, the idea of dynamic programming can reduce the amount of calculation.


Usually many subproblems are very similar, so the dynamic programming method tries to solve each subproblem only once, which has the function of natural pruning, thus reducing the amount of calculation: once the solution of a given subproblem has been worked out, it will be memorized and stored, so that the next time the solution of the same subproblem is needed, it can be directly looked up in the table. This is particularly useful when the number of repeating subproblems grows exponentially with respect to the size of the input.

Fibonacci sequence

It is defined as: starting from 0 and 1, each successive digit is the sum of the preceding two digits.

1. Recursion of violence

Still using the idea of dynamic programming, we can get the state transition equation:

$$ f(n)=f(n-1)+f(n-2) $$

Here is the code implementation:

Def fib(n): base case if n in (1,2): return 1 return fib(n-1) + fib(n-2)

In this way, violent recursion is actually very inefficient. If we draw the recursion tree, we can clearly see that:

When calculating f(20), f(19) and f(18) are calculated, and when calculating f(19), f(18) is calculated again, which leads to low efficiency of repeated calculation.

2. Memo optimization

Use an array or dictionary to store values that have already been computed, acting as a cache to reduce double counting.

The code is implemented as follows:

Def fib(n, TB: List): base case if n in (1,2): return 1 if TB [n-1] is None: tb[n-1] = fib(n-1, tb) + fib(n-2, tb) return tb[n-1]

The recursive graph is as follows:

In this way, the redundant computation in the recursion tree is removed, and the time complexity is optimized from O(n^2) to O(n), which can be said to be a dimensionality reduction blow.

According to the direction of thinking about solving the problem, this is a top-down way. From the final result, that is, the root node of the recursion tree, the calculation is recursively downward until the return, as shown in the figure below:

3. Iterate the dp array from the bottom up

In fact, we can also iteratively solve the problem from the bottom up, from the minimum f(1) and f(2) to derive f(20). The code is as follows:

Def fib(n): if n in (1,2): return 1 dp = [0] * (n+1) dp[1]=dp[2]=1 for I in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

4. DP array space optimization

We observe that the results of each time are actually only related to the results of the first two, so we can simplify the space by storing only the first two results.

Def fib(n): if n in (1,2): return 1 dp_1 = dp_2= 1 for I in range(3, n+1): dp_1,dp_2=dp_1+dp_2,dp_1 return dp_1

Small change problem

Here’s the question: I’m going to give you k coins, each of which has a denomination of C1, C2… CK, the number of each hard coin is infinite, and then give a total amount, and ask you how many coins you need to raise this amount at least. If it is impossible to raise this amount, the algorithm will return -1.

Think top down

Thinking steps:

  1. This problem contains the characteristics of optimal substructure, and the subproblems are independent of each other, so it is a dynamic programming problem.
  2. Define the correct dp function,dp(amount)=nThis is the minimum amount of coins needed to get the amount of money, which is actually pretty easy to list, because there’s only one variable in the problem, amount, so what we want to solve for is the minimum number of coins, so let’s call it n, and then we can easily define dp.

  3. List the state transition equation:

    $$ dp(amount)=min(dp(amount-c1)+1, dp(amount-c2)+1, …) $$

  4. Note the boundary conditions. The only case where the amount cannot be rounded up is when the amount is smaller than the smallest coin and is not zero.

The code is implemented as follows:

From typing import List def min_coin_num(coins: List, amount: int): def dp(n): Return 0 if n < 0: return -1 ret = float("inf") for coin in coins: sub_problem = dp(n - coin) if sub_problem == -1: continue ret = min(ret, sub_problem + 1) return ret if ret ! = float("inf") else -1 return dp(amount)

So if you plot the recursion tree, you can see that there’s still some redundancy, and you can optimize it a little bit, and you can keep a memo of what you’ve already computed, so you don’t have to do it again the next time you do it.

Optimized code:

Def min_coin_num(coins: List, amount: int): memo = [None] * (amount + 1) def dp(n): If n < 0 if n < 0 if n < 0 if n < 0 if n < 0 if n < 0 if n < 0 if n < 0 if n < 0 if n < 0 Return -1 ret = float("inf") for coin in coins: sub_problem = dp(n-coin) if sub_problem == -1: ret = float("inf") for coin in coins: sub_problem = dp(n-coin) Continue ret = min(ret, sub_problem + 1) # memo[n] = ret if ret! = float("inf") else -1 return memo[n] return dp(amount)

We’re using arrays as memos, and we’re actually using dictionaries the same way.

Think bottom-up

In general, top-down recursion is used. The idea is to recursively break down the final problem into subproblems. Similarly, we can calculate the result from the bottom up, and go from the initial situation up through a finite number of iterations to get the final result.

Code implementation:

Def min_coin_num(coins: List, amount: int): dp = [float("inf")] * (amount + 1) dp[0] = 0 for n in range(amount + 1): for coin in coins: if coin <= n: dp[n] = min(dp[n], dp[n - coin] + 1) return dp[amount] if dp[amount] ! = float("inf") else -1

Methods to summarize

Applicable case: optimal subproblems, and the subproblems are independent of each other.

Directions for thinking: 1. Top-down recursion; 2. 2. Bottom-up finite iteration.

State transition equation: The general form is $dp(variable 1, variable 2…). = Target result $

Optimization method: array or dictionary as a memorandum to record the results of the intermediate subproblems, to avoid double calculation.