This is the 30th day of my participation in the August Text Challenge.More challenges in August
Dynamic programming is a data structure and algorithm of plate in the most difficult part of a lot of people just hearing the topic is the dynamic programming, an instant generates fear in the heart, and dynamic programming is the interviewer to prefer a module, a consortium in both clubs recruit school recruit is a big part of the interview, to tell the truth, I recently also in study of dynamic programming, I will sort out the relevant content of dynamic programming from 0 to 1 from a small white point of view, from brute force cracking to memorization search to dynamic programming, step by step, and conquer dynamic programming in one stroke. I hope it will be helpful to you as you read this article.
The first part
Fibonacci numbers
F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)
It’s easy to write code like this:
int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
} else {
return fib(n - 1) + fib(n - 2); }}Copy the codeIf we calculate FIB (5), its recursion tree looks like the following:
Mnemonic search
In order to avoid repeated calculation, we can store the calculated result in a container. If the value we need has been calculated before, we can return it directly without repeated calculation.
int fib(int n) {
if (n < 0) {
throw new IllegalArgumentException("n value must be > 0");
}
int[] memo = new int[n + 1];
// Initialize the array with values -1
// The reason it initializes to -1 is because fib can't evaluate to -1, it's always greater than or equal to 0
for (int i = 0; i < memo.length; i++) {
memo[i] = -1;
}
return fibCore(n, memo);
}
int fibCore(int n, int[] memo) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (memo[n] == -1) {
// This value has not been calculated before, so it needs to be calculated
memo[n] = fibCore(n - 1, memo) + fibCore(n - 2, memo);
}
return memo[n];
}
Copy the codeSo this is a top-down approach to the problem, where we don’t count fib of n, but fib of n minus 1 and fib of n minus 2, and we keep going until we get f of 0 or f of 1.
Dynamic programming
We can do the reverse, top down, by computing fib of 0,fib of 1,fib of 2… Fib (n), the code is as follows:
int fib(int n) {
if (n < 0) {
throw new IllegalArgumentException("n value must be > 0");
}
int[] memo = new int[n + 1];
for (int i = 0; i <= n; i++) {
if (i <= 1) {
memo[i] = i;
} else {
memo[i] = memo[i - 1] + memo[i - 2]; }}return memo[n];
}
Copy the codeDynamic programming dissolves the original problem into several sub-problems and saves the answers of the sub-problems at the same time, so that the solution of each sub-problem can be solved only once, and finally the answer of the original problem can be obtained.
Climb the stairs
The title
If I have a staircase, and I can go up one or two at a time, how many ways can I go up n steps?
We go up to the NTH step we might be on the n-1 step or the N-2 step, and we go up to the n-1 step we might be on the N-1-1 or the N-1-2 step. And so on and so forth until we get to the second step or the first step, when we get to the first step, there’s only one way, and when we get to the second step it could be 1+1 or 2, so there’s two ways. So our code could look something like this.
Brute force
int climb(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
// Go straight up 2 steps or one step
return 2;
}
return climb(n - 1) + climb(n - 2);
}
Copy the codeLet’s say we have only one way to climb the 0th step, but we don’t have one, so we can climb the 0th step by climbing (1)+climb(0), so our code looks like this:
int climb(int n) {
if (n <= 1) {
return 1;
}
return climb(n - 1) + climb(n - 2);
}
Copy the codeIf you’re careful, this is the Fibonacci sequence that we just wrote.
Triangle
Given a triangular array of numbers, choose a top-down path that minimizes the sum of all the numbers along the way (each step can only be moved to an adjacent cell) eg:
The minimum path is 2+3+5+1=11
MiniMum Path Sum
Given an M *n matrix, where each cell contains a non-negative integer, find a path from the top left to the bottom right that minimizes the sum of the paths along the way.
You can only move down or to the right at a time.
The second part
Given a positive integer n, it can be divided into the sum of multiple numbers. To maximize the number of numbers, find the method of splitting, (at least into two numbers). Returns the maximum number of flights.
If n=2, return 1 (2=1+1). If n=10, return 36 (10=3+3+4).
Violent solution
Backtracking traversal splits a number, O(2^n)
- Here, segmentation 4 is taken as an example, as shown below:
- Corresponding to segmentation n, as shown in the following figure:
The corresponding code is as follows:
int breakInteger(int n) {
if (n == 1) {
return 1;
}
int res = -1;
for (int i = 1; i < n - 1; i++) {
// I *(n-i) specifies the reason for the comparison
// Because breakInteger must split a number into two parts,
// So, if we just split n into two parts and don't want to divide it further down, that's I times n minus I.
res = max(res, i * (n - i), i * breakInteger(n - i));
}
return res;
}
int max(int a, int b, int c) {
return Integer.max(a, Integer.max(b, c));
}
Copy the codeMnemonic search
In the figure of n segmentation above, we can see that “overlapping sub-problems” also occur in this problem, so we can further conduct “memorization search” to record the calculated results and avoid repeated operation.
int breakInteger(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return breakIntegerCore(n, memo);
}
int breakIntegerCore(int n, int[] memo) {
if (n == 1) {
return 1;
}
if(memo[n] ! = -1) {
return memo[n];
}
int res = -1;
for (int i = 1; i < n - 1; i++) {
// I *(n-i) specifies the reason for the comparison
// Because breakInteger must split a number into two parts,
// So, if we just split n into two parts and don't want to divide it further down, that's I times n minus I.
res = max(res, i * (n - i), i * breakIntegerCore(n - i, memo));
}
memo[n] = res;
return res;
}
int max(int a, int b, int c) {
return Integer.max(a, Integer.max(b, c));
}
Copy the codeDynamic programming
Solve from the bottom up
int integerBreak(int n) {
// The memo[I] is used to store the largest product of the number I after splitting it into at least two parts
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
memo[1] = 1;
for (int i = 2; i <= n; i++) {
/ / calculate the memo [I]
for (int j = 1; j < i - 1; j++) {
// i*(i-j)memo[i] = max(memo[i], j * (i - j), j * memo[i - j]); }}return memo[n];
}
Copy the codePerfect Squares
Given a positive integer, find the fewest perfect squares such that their sum is n
eg: 12=4+4+4 13=4+9
Decode Ways
A character string containing a-z letters. Each character can correspond to A number ranging from 1 to 26, for example, A-1, B-2… Z – 26. Given a string of numbers and asked, how many ways can we parse this string of numbers?
Eg: AB can be resolved to (1,2) or 12, returning 2
Unique path
I have a robot that starts at the upper left corner of an M by n matrix, and to reach the lower Angle of the matrix, the robot can only move to the right or down at any one time, and I ask you how many different paths there are.
I have a robot that starts at the upper left corner of an M by n matrix, and to reach the lower Angle of the matrix, the robot can only move to the right or down at any one time, and I ask you how many different paths there are.The third part
House Robber
Suppose you are a professional thief and you want to rob all the houses in a street. Each house has different treasures, but if you steal two houses in a row, the alarm system will be triggered and programmed to figure out the maximum value of treasures you can steal
Eg:,4,1,2 [3] – > 6 [1 and 3, (4), (2)],3,1,2 [4] — > 6 [(4), 3, 1, (2)]
Violent solution
Check all combinations of houses, check for neighboring houses for each combination, if not, record its value and find the maximum. Time complexity: O((2^n)*n)
The recursion tree is as follows
State transition equation
- We call the definition of a recursive function that considers stealing a house in the range [x…n-1], and we call it **” state “**
f(0)=max{ v(0)+f(2), v(1)+f(3), v(2)+f(4),... v(n-3)+f(n-1), v(n-2), v(n-1)}Copy the codeThe function f(x) above represents the maximum amount of treasure to steal from house X, and v(y) represents the value of house Y removed. Consider the maximum value of stolen treasures from house 0.
- It could be stealing the treasure from House 0 plus the maximum amount of treasure from house 2;
- It could be stealing the treasure from House 1 plus the maximum amount of treasure from house 3;
- It could be stealing the treasure from House 2 plus the maximum amount of treasure from house 4;
.
- It could be stealing the treasure from house N-3, plus the maximum value of the treasure from house N-1;
- It could be stealing the treasure of house N-2, plus considering the maximum value of the treasure stolen from house N, thinking that house N does not exist, so it is ignored.
- It could be stealing the treasure of house N-1…
The solution to this problem is to choose the maximum of these options. That’s the equation up here. This equation is called **” state transition equation “**.
Brute force
/** * Gets the maximum number of treasures **@paramHouse, house *@returnGet the maximum treasure */
public int robs(int[] house) {
return tryRobs(0, house);
}
/** * Attempts to loot the maximum number of treasures **@paramIndex starts thinking about the number of the house to rob *@paramHouse, house *@returnAttempt to loot the maximum number of treasures */
private int tryRobs(int index, int[] house) {
if (index >= house.length) {
// Attempted to rob a house whose number exceeded the maximum number
return 0;
}
// Record the maximum number of houses robbed this time
int res = -1;
for (int i = index; i < house.length; i++) {
res = Integer.max(res, house[i] + tryRobs(i + 2, house));
}
return res;
}
Copy the codeMnemonic search
/** * Gets the maximum number of treasures **@paramHouse, house *@returnGet the maximum treasure */
public int robs(int[] house) {
int[] memo = new int[house.length];
Arrays.fill(memo, -1);
return tryRobsWithMemo(0, house, memo);
}
/** * Attempt to loot the maximum treasure with mnemonic search **@paramIndex starts thinking about the number of the house to rob *@paramHouse, house *@paramMemo Memo [X] starts thinking about robbing house X for the maximum number of treasures *@returnAttempt to loot the maximum number of treasures */
private int tryRobsWithMemo(int index, int[] house, int[] memo) {
if (index >= house.length) {
// Attempted to rob a house whose number exceeded the maximum number
return 0;
}
if(memo[index] ! = -1) {
return memo[index];
}
// Record the maximum number of houses robbed this time
int res = -1;
for (int i = index; i < house.length; i++) {
res = Integer.max(res, house[i] + tryRobsWithMemo(i + 2, house,memo));
}
memo[index] = res;
return res;
}
Copy the codeDynamic programming
int rob(int[] house) {
int length = house.length;
if (length == 0) {
return 0;
}
int[] memo = new int[length];
Arrays.fill(memo, -1);
memo[length - 1] = house[length - 1];
for (int i = length - 2; i >= 0; i--) {
// Calculate the maximum value of memo[I]
for (int j = i; j < length; j++) {
memo[i] = Integer.max(memo[i], house[j] + (j + 2 < length ? memo[j + 2] : 0)); }}return memo[0];
}
Copy the codeexpand
- Consider stealing treasures from houses in [x…n-1] range
- Consider stealing treasures from houses in [0…x] range
House Robber II
Same as the Hourse acquirers, but what is the maximum value of a circular street, given an array in which the first and last elements are neighbors, that can steal property without touching the alarm?
Best Time To Buy And Sell Stock with Cooldown
Given an array that represents the price of a stock on each day. Design a trading algorithm, automatic trading in these days, requirements: only one operation per day, after buying stocks, the next day is not to buy. Ask how to trade to maximize profits.
Eg: price=[1,2,3,0,2] the best trading method is [buy, sell, colldown, buy, sell], the profit is 3, the algorithm returns 3