This paper is divided into three parts:
- What is dynamic programming?
- What scenarios are suitable for dynamic programming?
- How to write dynamic programming code?
What is dynamic programming?
Dynamic programming (DP) is a mathematical method to solve the optimization of decision-making process. It solves complex problems by decomposing original problems into relatively simple sub-problems. Dynamic programming is often applied to problems with overlapping subproblems and optimal substructural properties. Dynamic programming is a method that uses space to change time to solve the optimal solution. Generally, the time complexity in programming is less than that of conventional solutions (such as violent solution and backtracking algorithm).
applicable
Dynamic programming can only be applied to problems with optimal substructures. Optimal substructure means that the local optimal solution solves the global optimal solution.
- Optimal substructure properties. A problem is said to have optimal submechanism properties (that is, to satisfy the optimization principle) if the optimal solution of the problem contains a subproblem whose solution is also optimal. Optimal substructure properties provide important clues for dynamic programming algorithms to solve problems.
- No aftereffect. That is, once the solution of the subproblem is determined, it does not change, and is not affected by the solution decision of the larger problem that contains it later.
- Overlapping properties of subproblems. Overlapping subproblems nature refers to the top-down using a recursive algorithm to solve the problem, each subproblem is not always a new problem, some sub-problems will be repeated many times calculation, dynamic programming algorithm exploits the overlapping nature of these subproblems, calculated only once for each child problem, then the calculation results are stored in a table, It is more efficient to simply look at the results in the table when you need to compute a subproblem that has already been computed.
How to write dynamic programming code?
Let’s look at a couple of examples.
Stair climbing problem
Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?
Note: given n is a positive integer.
Solution 1: violent solution
In the violent solution, we are going to combine all possible steps, namely 1 and 2. At each step we recursively call the original function to simulate climbing steps 1 and 2, and return the sum of the return values of the two functions.
ClimbStairs (I, n) = climbStairs(I +1, n) + climbStairs(I +2, n)Copy the code// Swift implements the algorithm
func climbStairs(_ n: Int) -> Int {
return climbStairs(0, n: n)
}
func climbStairs(_ i: Int, n: Int) -> Int {
if i > n {
return 0
}
if i == n {
return 1
}
return climbStairs(i + 1, n: n) + climbStairs(i + 2, n: n)
}
Copy the codeComplexity analysis:
-
Time complexity: O(2^n). Tree recursion is of size 2 to the n
When n is equal to 5, the recursion tree looks like this
- Space complexity: O(n). Recursion trees can be as deep as n.
Solution two: memorization recursion
Using the brute force method, the results of each step are redundant. Alternatively, we could store the result of each step in the Memo array and return the result directly from the Memo array each time the function is called again. With the help of the Memo array, we get a repaired recursive tree that is reduced to n.
func climbStairs(_ n: Int) -> Int {
var memo = Array(repeating: 0.count: n)
return climbStairs(0, n: n, memo: &memo)
}
func climbStairs(_ i: Int, n: Int, memo: inout Array<Int>) -> Int {
if i > n {
return 0
}
if i == n {
return 1
}
if memo[i] > 0 {
return memo[i]
}
memo[i] = climbStairs(i + 1, n: n, memo: &memo) + climbStairs(i + 2, n: n, memo: &memo);
return memo[i]
}
Copy the codeComplexity analysis:
- Time complexity: O(n). The size of the tree recursion is reduced to n
- Space complexity: O(n). The recursion tree has a depth of n
Solution three: dynamic programming
It is not difficult to find that this problem can be decomposed into some subproblems containing optimal substructures, that is, its optimal solution can be effectively constructed from the optimal solution of the subproblems, we can use dynamic programming to solve this problem.
Order I can be obtained in two ways:
- In the first
(i-1)Step back one step. - In the first
(i-2)The order goes back two steps. So, the total number of ways to get to order I is 1(i-1)Order and(i-2)Sum of order method numbers.
Let dp[I] represent the number of methods that can reach the i-th order: dp[I] = dp[i-1] + dp[i-2]
func climbStairs(_ n: Int) -> Int {
if n == 1 {
return 1
}
var dp = Array(repeating: 0.count: n+1)
dp[1] = 1
dp[2] = 2
for i in 3. n { dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}
Copy the codeThrough this example, we can summarize the thinking process of dynamic planning as follows: The thinking process of dynamic planning can be summarized as: big things become small, small things become small.
Roll with the punches
A larger problem, dividing a complex problem into smaller problems by finding overlaps with subproblems, is also a state shift.
hush
Small problems are usually solved by initialization, directly computed results;
Specific steps:
- Break down big problems into sub-problems
- Deterministic state representation
- Determine state transition
- Consider the initial state and the boundary case
Some examples of dynamic programming
Change to round off
If we have several $1, $3 and $5 coins, how can we make $11 with the least amount of coins?
- Break the big problem down into sub-problems: Since there are many cases in which 11 yuan is made up of 1, 3 and 5 yuan coins, it is difficult to enumrate all the cases by violence. We can divide the problem into several sub-problems, and use dp[I] to represent the number of coins needed to make up I yuan coins. dp[i] = min{dp[i-1]+1, dp[i-3]+1, dp[1-5]+1}
- State: dp[I]
- State transition equation: pseudocode representation
if i < 3 dp[i] = dp[i-1] + 1
else
if i >= 5 dp[i] = min{dp[i-1]+1, dp[i-3]+1, dp[1-5]+1}
else dp[i] = min{dp[i-1]+1, dp[i-3]+1}
Copy the code- Consider the initial state and the boundary case when
i = 0, 0 coins can be pawnedi = 1, i = 3, i = 5, only 1 coin is needed to be the optimal solution
The code is as follows:
func countMoney(_ n: Int) -> Int {
if n == 0 {
return 0
}
var dp = Array(repeating: 0.count: n+1)
dp[1] = 1
dp[3] = 1
dp[5] = 1
for i in 1. n {if i < 3 {
dp[i] = dp[i-1] + 1
} else
if i >= 5 {
dp[i] = min(dp[i-1] + 1, dp[i-3] +1, dp[i-5] +1)}else
{
dp[i] = min(dp[i-1] + 1, dp[i-3] + 1)}}return dp[n]
}
Copy the codeNow, let’s do one more problem
Knapsack problem
So this guy went out in the woods and found a bunch of gems, and he counted them, and there were n of them. But the only thing he could carry was a backpack, size C. This guy lines up n gems and numbers them: 0,1,2… , n – 1. The ith gem corresponds to V[I](V for volume) and W[I](W for worth). After arranging, the guy began to think: the backpack can only hold something of size C, so what gems should I put in to get the most benefit?
To analyze the problem, we define a function F(I, j), which represents the maximum value of the stones that can be held, and I, which represents the number of stones that can be held, is an array (0, 1, 2… , I), j represents the capacity of the backpack. Suppose, we have 6 and gems, with volumes V = [2, 2, 6, 5, 4, 3] respectively, and corresponding values W = [6, 3, 5, 4, 6, 2] respectively.
When backpack capacity C = 1, then F(0, 1) = 0; F(1, 1) = 0; . ; F(5, 1) = 0;
When backpack capacity C = 2, then F(0, 2) = 6; F(1, 2) = 6; . ; F(5, 2) = 6;
When backpack capacity C = 3, then F(0, 3) = 6; F(1, 3) = 6; . ; F(5, 3) = 6;
From this, we can conclude that the maximum value of gemstones can be carried in a backpack is related to the number of gemstones and backpack capacity.
Our goal is to figure out how to fit the most valuable n stones into a backpack.
Let’s make an assumption: start with the indices at 1. The subscripts of n gems are 1,2,3… ,n
- The NTH gem, it’s not the gem we want, so
1, 2, 3,... ,n-1, we can work out the maximum value we need, which can be expressed as the above function expression:F(n-1, C); - Assuming that the first
n1 gem is the gem we want, so the backpack should reduce the space of the NTH gem, and the remaining space can be used to store other gems, so the maximum value of the gem can be expressed as:F(n-1, C-V[n]); Then, the maximum value that a backpack with space C can carry isF(n-1, C-V[n])+W[n]
There are only two cases, so if we combine these two cases, the maximum value is the final value of the function that we want to solve for. F(n, C) = MAX(F(n-1, C), F(n-1, C-V[n])+W[n])
So, the maximum value of n stones is related to the maximum value of n minus 1 stones.
Follow the steps we described above to solve:
- Break a big problem into sub-problems: We’ve broken a big problem into a small problem.
- Status means:
F(n, C) - Determine the state transition equation:
F(n, C) = MAX(F(n-1, C), F(n-1, C-V[n])+W[n]) - Considering the initial state and the boundary case,
F(0, 0) = 0;
The code implementation is as follows:
struct Diamond {
var id: String
var volume: Int
var value: Int
var isSelected = false
init(_ volume: Int, value: Int, id: String) {
self.volume = volume
self.value = value
self.id = id
}
}
class Knapsack {
var number: Int // Number of items
var C: Int // Maximum size or weight of backpack
var diamonds = Array<Diamond> ()var V = Array<Array<Int> > ()init(number: Int.C: Int) {
self.C = C
self.number = number
// Initialize a two-dimensional array
self.V = initializeArray()
// Initializes the gem object
setDiamonds()
// Print an existing gem
printDiamonds()
}
// The initial gem array
func setDiamonds(a) {
for i in 0. number {if i == 0 {
diamonds.append(Diamond(0, value: 0, id: "0"))}else {
diamonds.append(Diamond(i + 1, value: i + 2, id: String(i)))
}
}
}
// Prints all gems
func printDiamonds(a) {
for diamond in diamonds {
print("id:\(diamond.id), value:\(diamond.value), volume:\(diamond.volume)")}}// Prints selected/unselected gems
func printDiamonds(_ selected: Bool) {
if selected {
print("The chosen gem:")}else {
print("The unchosen gem:")}for diamond in diamonds {
ifdiamond.isSelected == selected && diamond.volume ! =0 {
print("id:\(diamond.id), value:\(diamond.value), volume:\(diamond.volume)")}}}// Initialize the dp array
func initializeArray(a)- > [[Int]] {
var myArr = Array<Array<Int> > ()for _ in 0. number { myArr.append(Array(repeating: 0.count: C+1))}return myArr
}
func findOptimalSolution(a) -> Int {
// I = 0, j = 0 is the boundary condition, when initialized, initialized to 0
// Populate a two-dimensional array
for i in 1. number {for j in 1.C {
if j < diamonds[i].volume {
// When there is not enough space to hold the gem, the value of the current element is the same as the value of the previous element
V[i][j] = V[i-1][j]
} else {
// When the remaining space is enough for the gem, it dynamically plans whether to select the gem
V[i][j] = max(V[i-1][j], V[i-1][j-diamonds[i].volume] + diamonds[i].value)
}
}
}
// The last element of the two-dimensional array is the maximum value
return V[number][C]}// Find which gems are selected
func findSelectedDiamonds(i: Int, j: Int) {
if i > 0 {
if V[i][j] == V[i-1][j] {
diamonds[i].isSelected = false
findSelectedDiamonds(i: i-1, j: j)
} else {
if j - diamonds[i].volume >= 0 && V[i][j] == V[i-1][j-diamonds[i].volume] + diamonds[i].value {
diamonds[i].isSelected = true
findSelectedDiamonds(i: i - 1, j: j - diamonds[i].volume)
}
}
}
}
}
Copy the codeAs shown in the table below:
| Backpack size: 1 | Backpack size: 2 | Backpack size: 3 | Backpack size: 4 | Backpack size: 5 | Backpack size: 6 | Backpack size: 7 | |
|---|---|---|---|---|---|---|---|
Gem 1(volume = 2, worth = 6) |
0 | 6 | 6 | 6 | 6 | 6 | 6 |
2 gems(volume = 2, worth = 3) |
0 | 6 | 6 | 9 | 9 | 9 | 9 |
Gem 3(volume = 6, worth = 5) |
0 | 6 | 6 | 9 | 9 | 9 | 9 |
Gem 4(volume = 5, worth = 4) |
0 | 6 | 6 | 9 | 9 | 9 | 10 |
Gem 5(volume = 4, worth = 6) |
0 | 6 | 6 | 9 | 9 | 12 | 12 |
Longest ascending subsequence (longest increasing subsequence)
A sequence has N numbers: A[1],A[2]… ,A[N], find the length of the longest non-descending subsequence.
Analyze the problem: we define an array dp, dp[I] stands for 0… The maximum ascending subsequence of the sequence between I, where I
dp[0] = 1, ([10])
dp[1] = 1, ([10, 9])
dp[2] = 2, ([10, 9, 2])
dp[3] = 2, ([10, 9, 2, 5])
dp[4] = 2, ([10, 9, 2, 5, 3])
dp[5] = 3, ([10, 9, 2, 5, 3, 7])
dp[6] = 4, ([10, 9, 2, 5, 3, 7, 101])
Copy the codeTo find dp(I), add one to the length of the subsequence that precedes I, with the last number not greater than A[I], and then extract the maximum length to be dp(I).
Follow the above steps to solve:
- Break the big problem down into sub-problems:
- Deterministic state:
dp[i] - Determine the state transition:
Dp [I] = Max (dp) [j] + 1, ∀ 0 or less j < I - Consider the initial state and boundary case:
dp[0] = 1
The code is as follows:
/* * This method relies on the fact that the longest incrementing subsequence before index I in a given array is independent of the elements appearing later in the array. Therefore, if we know the length of the index LIS to I, we can calculate the possible length of LIS based on the fact that the element whose index j is 0≤j≤(I +1) contains (I +1) elements. * We use a DP array to store the required data. Dp [I] represents the length of the longest incrementing subsequence possible if only the array elements indexed by I are considered and must contain I elements. To find dp[I], we need to try to append the current element (nums[I]) to the (i-1) index (including the (i-1) index) in each possible increasing subsequence, so that the new sequence formed by adding the current element is also an increasing subsequence. Therefore, we can easily determine DP [I] using: * dp[I] = Max (dp[j])+1, ∀0≤j< I * Finally, the maximum value of all DP [I] to determine the final result. * LIS.length = Max (dp[I]), 0≤ J < I * Time complexity: two-layer cycle O(n^2) * Space complexity: O(n) */
func lengthOfLIS(_ nums: [Int]) -> Int {
if nums.count= =0 {
return 0
}
var dp = Array(repeating: 0.count: nums.count)
dp[0] = 1
var maxAns = 1
for i in 1..<dp.count {
var maxVal = 0
for j in 0..<i {
if nums[i] > nums[j] {
maxVal = max(maxVal, dp[j])
}
}
dp[i] = maxVal + 1
maxAns = max(maxAns, dp[i])
}
return maxAns
}
Copy the codeTwo dimensional dynamic programming problem
There are N by M cells in the plane, and each cell holds a certain number of apples. You start at the upper left corner of the grid, each step can only go down or to the right, each time you go to the grid to collect the apples, so that, how many apples can you collect.
I represents the row and j represents the column. Solve as follows:
- Break the big problem down into sub-problems:
dp[i][j]anddp[i-1][j]anddp[i][j-1]About, - Deterministic state:
dp[i][j] - Determine the state transition:
dp[i][j] = A[i][j] + max(dp[i-1][j], if i > 0; dp[i][j-1], if j > 0) - Consider the initial state and boundary case:
dp[0][0] = A[0][0]
Pseudo-code implementation:
int[][] dp
for i = 0; i < N - 1; i++
for j = 0; j < M - 1; j++
if i == 0 dp[i][j] = dp[i][j-1] + A[i][j]
if j == 0 dp[i][j] = dp[i-1][j] + A[i][j]
else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[N-1][M-1]
Copy the codeReference links:
- Comics: What is Dynamic programming?
- Dynamic programming: From novice to expert
- Knapsack Problem of Dynamic Programming (1)