1. Algorithm
1.1 dynamic planning
1.1. 1 simple topic
53. Maximum subsequence sum
Given an integer array nums, find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum.
- Method 1
/*
Use f(i) to represent the "maximum sum of continuous subarrays" ending with the ith number
Dynamic programming transfer equation: f(i)=max{f(i − 1)+nums[i],nums[i]}
*/
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int result = dp[0];
for(int i=1;i<nums.length;++i){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
result = dp[i] > result ? dp[i] : result;
}
return result;
}
}
- Method 2
//f(i) is only related to f(i − 1). You can use only one variable pre to maintain the value of f(i-1) for the current f(i)
//After optimization
class Solution {
public int maxSubArray(int[] nums) {
int maxArr = nums[0];
int pre = 0;
for (int num:nums) {
pre = Math.max(pre+num,num);
maxArr = Math.max(maxArr,pre);
}
return maxArr;
}
}
70. Climb stairs
Suppose you are climbing stairs. You need n steps to reach the roof.
You can climb one or two steps at a time. How many different ways can you climb to the roof?
Note: given n is a positive integer.
- Method 1: recursion (beyond the time limit)
/*
Recursion is important to analyze the core of recursion. Don't indulge in the process of recursion
analysis:
Use f(i) to indicate how many walking methods there are when n=i
n=1 ->Take a step -> f(1) = 1
n=2 -> (1)Step by step (2) take two steps directly -> f(2) = 2
n=3 -> (1)First arrive at f(1), and then take two steps directly from f(1)
-> (2)First arrive at f(2), then take a step from f(2) - > F (3) = f (1) + f(2)
n=4 -> (1)First get to f(2) and then take two steps directly from f(2)
-> (2)First arrive at f(3), then take a step from f(3) - > F (4) = f (2) + f(3)
..........
n=i -> (1)First arrive at f(i-2), and then take two steps directly from f(i-2)
-> (2)First arrive at f(i-1), then take a step from f(i-1) - > F (I) = f (I-2) + f(i-1)
*/
class Solution{
public int f(int n){
//Termination condition of recursion
if(n == 1 || n== 2){
return n;
}
return f(n-2) + f(n-1);
}
}
- Method 2: iteration
/*
analysis:
Use f(i) to indicate how many walking methods there are when n=i
Use one to save the last step and two to save the last two steps
n=1 ->Take a step -> f(1) = 1
n=2 -> (1)Step by step (2) take two steps directly -> f(2) = 2
n=3 -> (1)First arrive at f(1), and then take two steps directly from f(1)
-> (2)Arrive at f(2) first, and then take a step from f(2)
->f(3) = two + one
->f(3) = f(1) + f(2)
->two = f(1);one = f(2)
n=4 -> (1)First get to f(2) and then take two steps directly from f(2)
-> (2)Arrive at f(3) first, and then take a step from f(3)
->f(4) = two + one
->f(4) = f(2) + f(3)
->two = f(2);one = f(3)
..........
n=i -> (1)First arrive at f(i-2), and then take two steps directly from f(i-2)
-> (2)Arrive at f(i-1) first, and then take a step from f(i-1)
->f(i) = two + one
->f(i) = f(i-2) + f(i-1)
->two = f(i-2);one = f(i-1)
*/
class Solution{
public int loop(int n){
if(n == 1 || n== 2){
return n;
}
int two = 1;//Initialize to the method of walking to the first step
int one = 2;//Initialize to the method of walking to the second step
int sum = 0;//Save the general route
for(int i=3;i<=n;++i){
//Last two steps + last step
sum = two + one;
two = one;
one = sum;
}
return sum;
}
}
- Method 3: dynamic programming
/*
Use f(i) to represent the number of schemes for climbing to the i-th step
Dynamic programming transfer equation: f(i) = f(i-1) + f(i-2)
f(i) It is only related to f(i-1) and f(i-2), so we can use the idea of rolling array to optimize the space complexity
*/
class Solution {
public int dp(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
118. Yanghui triangle
Given a nonnegative integer numRows, the first numRows of the Yang Hui triangle are generated.
In the Yang Hui triangle, each number is the sum of its upper left and upper right numbers.
1 <= numRows <= 30
/*
The analysis shows that:
The values in the first column are all 1
The value is 1 when the row and column numbers are equal
No, arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
int[][] arr = new int[numRows][numRows];
List<List<Integer>> res = new ArrayList<List<Integer>>();
for (int i = 0; i < arr.length; i++) {
List<Integer> list = new ArrayList<Integer>();
for (int j = 0; j <= i; j++) {
if (j == 0){
arr[i][j] = 1;
}else if (i == j){
arr[i][j] = 1;
}else{
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
list.add(arr[i][j]);
}
res.add(list);
}
return res;
}
}
121. The best time to buy stocks
Given an array of prices, its ith element prices[i] represents the price of a given stock on day I.
You can only choose to buy this stock one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.
Return the maximum profit you can make from this transaction. If you can't make any profit, return 0.
1 <= prices.length <= 105
0 <= prices[i] <= 104
- Method 1
/*
1.Determine the meaning of dp array and subscript
dp[i][0] Indicates the maximum cash received from not holding shares on day i
dp[i][1] Represents the maximum cash received from holding shares on day i
int[][] dp = new int[price.length][2];
2.Determine recurrence formula
If you don't hold stocks on day I, that is dp[i][0], you can also push it from two states
If you don't hold stocks on day i-1, keep the status quo. The cash obtained is the cash obtained from not holding stocks yesterday, that is: dp[i - 1][0]
The cash from selling stocks on the I day is the cash from selling stocks at today's good price, namely: prices[i] + dp[i - 1][1]
dp[i][0]Take the maximum, dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
If you hold stocks on day I, i.e. dp[i][1], it can be deduced from two states
If you hold stocks on day i-1, keep the status quo. The cash you get is the cash you get from holding stocks yesterday, that is: dp[i - 1][1]
The cash from buying stocks on day I is the cash from buying today's stocks, that is: - prices[i]
Then dp[i][0] should choose the one with the largest cash, so dp[i][1] = max(dp[i - 1][0], -prices[i]);
3.dp How to initialize an array
The recursive formula dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]); And dp[i][1] = max(dp[i - 1][0], -prices[i]); It can be seen that
The basis is derived from dp[0][0] and dp[0][1].
dp[0][0]It means that no stock is held on day 0. If no stock is held, then cash is 0, so dp[0][0] = 0;
dp[0][1]It means holding stocks on day 0. At this time, holding stocks must be buying stocks. Because it is impossible to push them out the previous day, dp[0][1] = -prices[0];
4.Determine traversal order
It can be seen from the recurrence formula that dp[i] is derived from dp[i - 1], so it must traverse from front to back.
5.final result
Finally, to get the maximum return, the final state must be not holding stocks, so the final result is dp[prices.length-1][0]
*/
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1;i<prices.length;++i){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
}
return dp[prices.length-1][0];
}
}
- Method 2
/*
Optimize method 1
It can be seen from the recurrence formula that dp[i] only depends on the state of dp[i - 1].
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
Then we only need to record the current day's dp status and the previous day's dp status. We can use the scrolling array to save space
*/
class Solution {
public int maxProfit(int[] prices) {
int notHold = 0;
int hold = -prices[0];
for(int i=1;i<prices.length;++i){
int not = notHold;
int yes = hold;
not = Math.max(not,yes+prices[i]);
yes = Math.max(yes,-prices[i]);
notHold = not;
hold = yes;
}
return notHold;
}
}
122. The best time to buy and sell stocks II
Give an array prices, where prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete as many transactions as possible (buying and selling a stock multiple times).
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
- Method 1
/*
1.Determine the meaning of dp array and subscript
dp[i][0] Indicates the maximum cash received from not holding shares on day i
dp[i][1] Represents the maximum cash received from holding shares on day i
int[][] dp = new int[price.length][2];
2.Determine recurrence formula
If you don't hold stocks on day I, that is dp[i][0], you can also push it from two states
If you don't hold stocks on day i-1, keep the status quo. The cash obtained is the cash obtained from not holding stocks yesterday, that is: dp[i - 1][0]
The cash from selling stocks on the I day is the cash from selling stocks at today's good price, namely: prices[i] + dp[i - 1][1]
dp[i][0]Take the maximum, dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
If you hold stocks on day I, i.e. dp[i][1], it can be deduced from two states
If you hold stocks on day i-1, keep the status quo. The cash you get is the cash you get from holding stocks yesterday, that is: dp[i - 1][1]
Buy stocks on day I (it means that you don't hold stocks on day i-1). The cash obtained is the sum of the cash obtained after buying today's stocks and the cash obtained without holding stocks on day I-1, that is, dp[i-1][0]-prices[i]
Then dp[i][0] should choose the one with the largest cash, so dp[i][1] = max(dp[i - 1][0], dp[i-1][0]-prices[i]);
3.dp How to initialize an array
The recursive formula dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]); And dp[i][1] = max(dp[i - 1][0], dp[i-1][0]-prices[i]); It can be seen that
The basis is derived from dp[0][0] and dp[0][1].
dp[0][0]It means that no stock is held on day 0. If no stock is held, then cash is 0, so dp[0][0] = 0;
dp[0][1]It means holding stocks on day 0. At this time, holding stocks must be buying stocks. Because it is impossible to push them out the previous day, dp[0][1] = -prices[0];
4.Determine traversal order
It can be seen from the recurrence formula that dp[i] is derived from dp[i - 1], so it must traverse from front to back.
5.final result
Finally, to get the maximum return, the final state must be not holding stocks, so the final result is dp[prices.length-1][0]
*/
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1;i<prices.length;++i){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.length-1][0];
}
}
- Method 2
/*
Optimize method 1
It can be seen from the recurrence formula that dp[i] only depends on the state of dp[i - 1].
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
Then we only need to record the current day's dp status and the previous day's dp status. We can use the scrolling array to save space
*/
class Solution {
public int maxProfit(int[] prices) {
int notHold = 0;
int hold = -prices[0];
for(int i=1;i<prices.length;++i){
int not = notHold;
int yes = hold;
not = Math.max(not,yes+prices[i]);
yes = Math.max(yes,not-prices[i]);
notHold = not;
hold = yes;
}
return notHold;
}
}
338. Bit counting
Give a nonnegative integer num. For each number i in the range of 0 ≤ i ≤ num, calculate the number of 1 in its binary number and return them as an array.
- Method 1: most significant bit
/*
1.Determine the meaning of dp array and its subscript
dp[i]Represents the number of bits of i
int[] dp = new int[num+1];
2.Determine recurrence formula
Use highBit to represent the most significant bit
If i is an integer power of 2:
It can be seen that i& (i-1) = 0, then highBit=i to update the current most significant bit;
dp[i] = dp[i-highBit] + 1;
For example:
When i=9
8 = 2*2*2 = 1000(Binary) - > most significant bit highBit = 8
1 = 0001 ->dp[1] = 1
9 = 1001 ->dp[9] = 2
It can be seen from the above that dp[9] = dp[9-8] + 1 = dp[1] + 1
3.initialization
It can be seen from the recursive formula that its basis is derived with highBit
It can be seen that the number of bits of 0 is 0;
Then int highBit=0;
4.Determine traversal order
It can be seen from the recurrence formula that dp[i] is derived from dp[i - highBit], so it must traverse from front to back.
5.The final array is the answer
*/
class Solution {
public int[] countBits(int n) {
int[] dp = new int[n+1];
int highBit = 0;
for(int i=1;i<=n;++i){
if((i&(i-1)) == 0){
highBit= i;
}
dp[i] = dp[i-highBit] + 1;
}
return dp;
}
}
- Method 2: least significant bit
/*
Analogy method 1:
Recurrence formula: dp[i] = dp[i/2] + (i%2) or DP [i] = DP [I > > 1] + (I & 1)
*/
class Solution {
public int[] countBits(int n) {
int[] dp = new int[n+1];
for(int i=1;i<=n;++i){
dp[i] = dp[i>>1] + (i&1);
}
return dp;
}
}
1.1. Second class topics
62. Different paths
A robot is located in the upper left corner of an m x n grid (the starting point is marked "Start" in the following figure).
The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the following image).
How many different paths are there altogether?
- Method 1
/*
1.Determine the subscript of dp array and its meaning
dp[i][j]Represents the number of paths from the upper left corner to the (i,j) position
int[][] dp = new int[m][n];
2.Determine recurrence formula
Since the robot can only move down or right, it must come from (i-1,j) or (i,j-1) to reach the position of (i,j)
Therefore, dp[i][j] = dp[i-1][j] + dp[i][j-1];
3.initialization
It should be noted that when i=0 or j=0, the number of paths is 1.
That is, dp[i][0] = 1,dp[0][j] = 1;
Obviously dp[0][0] = 1
4.Determine traversal order
From the recursive formula, we can see that dp[i][j] is derived from dp[i-1][j] and dp[i][j-1], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[m-1][n-1];
*/
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i=0;i<m;++i){
dp[i][0] = 1;
}
for(int i=1;i<n;++i){
dp[0][i] = 1;
}
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
- Method 2
/*
Optimize method 1:
Since dp[i][j] here is only related to dp[i-1][j] and dp[i][j-1], we can use the idea of rolling array to optimize the space complexity
1.Determine the subscript of dp array and its meaning
dp[j]Used to cache the current row
int[] dp = new int[n];
2.Determine recurrence formula
Since the robot can only move down or right, it must come from the previous line (j-1) or the current line (j) to reach line i
Then dp[j] = dp[j-1]+dp[j]
3.initialization
According to the recurrence formula, its basis is derived from dp[0]
So dp[0] = 1
4.Determine traversal order
From the recursive formula, we can see that dp[j] is derived from dp[j-1] and dp[j], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[n-1];
*/
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
dp[0] = 1;
for(int i=0;i<m;++i){
for(int j=1;j<n;++j){
dp[j] = dp[j-1] + dp[j];
}
}
return dp[n-1];
}
}
/*
Similarly
dp[j]Used to cache the current column
int[] dp = new int[m];
*/
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[m];
dp[0] = 1;
for(int i=0;i<n;++i){
for(int j=1;j<m;++j){
dp[j] = dp[j-1] + dp[j];
}
}
return dp[m-1];
}
}
63. Different paths II
A robot is located in the upper left corner of an m x n grid (the starting point is marked "Start" in the following figure).
The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the following image).
Now consider that there are obstacles in the mesh. How many different paths will there be from the upper left corner to the lower right corner?
m = obstacleGrid.length
n = obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1
- The problems of dynamic programming are divided into two categories: one is to find the optimal solution, the typical problem is the knapsack problem, and the other is the counting class. For example, the problem of the number of statistical schemes here has certain recursive properties. The recursive nature of the former is also called "optimal substructure" - that is, the optimal solution of the current problem depends on the optimal solution of the subproblem. Similarly, the number of schemes of the current problem depends on the number of schemes of the subproblem. Therefore, when we encounter the problem of finding the number of schemes, we can consider it in the direction of dynamic programming.
- Method 1
/*
1.Determine the subscript of dp array and its meaning
dp[i][j]Represents the number of paths from the upper left corner to the (i,j) position
int[][] dp = new int[m][n];
2.Determine recurrence formula
Since the robot can only move down or right, it must come from (i-1,j) or (i,j-1) to reach the position of (i,j)
If obstacleGrid[i][j] = 1, that is, there is an obstacle, then dp[i][j] = 0;
If obstacleGrid[i][j] = 0, that is, there is no obstacle, then dp[i][j] = dp[i-1][j] + dp[i][j-1];
3.initialization
When i=0, if there are obstacles in this line, the number of paths before the obstacle is 1, and the number of paths after the obstacle is 0
Similarly, when j=0, if there are obstacles in this column, the number of paths before the obstacles is 1, and the number of paths after the beginning of the obstacles is 0
4.Determine traversal order
From the recursive formula, we can see that dp[i][j] is derived from dp[i-1][j] and dp[i][j-1], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[m-1][n-1];
*/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for(int i=0;i<m;++i){
if(obstacleGrid[i][0] == 0){
dp[i][0] = 1;
}else{
break;
}
}
for(int i=0;i<n;++i){
if(obstacleGrid[0][i] == 0){
dp[0][i] = 1;
}else{
break;
}
}
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
if(obstacleGrid[i][j] == 1){
continue;
}
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
- Method 2
/*
Optimize method 1:
Since dp[i][j] here is only related to dp[i-1][j] and dp[i][j-1], we can use the idea of rolling array to optimize the space complexity
1.Determine the subscript of dp array and its meaning
dp[j]Used to cache the current row
int[] dp = new int[n];
2.Determine recurrence formula
Since the robot can only move down or right, it must come from the previous line (j-1) or the current line (j) to reach line i
If obstacleGrid[i][j] = 1, that is, there is an obstacle, dp[j] = 0;
If obstacleGrid[i][j] = 0, there is no obstacle,
At this time, also consider J-1 > = 0 and obstacleGrid[i][j-1] = 0
Then dp[j] = dp[j-1]+dp[j]
3.initialization
According to the recurrence formula, its basis is derived from dp[0]
So DP [0] = obstaclegrid [0] [0] = = 0? 1 : 0;
4.Determine traversal order
From the recursive formula, we can see that dp[j] is derived from dp[j-1] and dp[j], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[n-1];
*/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(obstacleGrid[i][j] == 1){
dp[j] = 0;
continue;
}
if(j-1>=0 && obstacleGrid[i][j-1] == 0){
dp[j] = dp[j-1]+dp[j];
}
}
}
return dp[n-1];
}
}
/*
Similarly
dp[j]Used to cache the current column
int[] dp = new int[m];
*/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[m];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(obstacleGrid[j][i] == 1){
dp[j] = 0;
continue;
}
if(j-1>=0 && obstacleGrid[j-1][i] == 0){
dp[j] = dp[j-1]+dp[j];
}
}
}
return dp[m-1];
}
}
64. Minimum path and
Given an m x n grid containing non negative integers, please find a path from the upper left corner to the lower right corner so that the sum of numbers on the path is the smallest.
Note: you can only move down or right one step at a time.
m = grid.length
n = grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
- Method 1
/*
1.Determine the subscript of dp array and its meaning
dp[i][j]Represents the minimum path from the upper left corner to (i,j) and
int[][] dp = new int[m][n];
2.Determine recurrence formula
Because it can only move down or right, if you want to reach the position of (i,j), you must come from (i-1,j) or (i,j-1)
Then when I > 0 and j > 0, dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
When I > 0 and j = 0, dp[i][0] = dp[i-1][0] + grid[i][0]
When I = 0 and j > 0, dp[0][j] = dp[0][j-1] + grid[0][j]
3.initialization
It can be seen from the recurrence formula that its basis is derived from dp[0][0], so dp[0][0] = grid[0][0];
4.Determine traversal order
From the recursive formula, we can see that dp[i][j] is derived from dp[i-1][j] and dp[i][j-1], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[m-1][n-1];
*/
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
for(int i=1;i<grid.length;++i){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1;i<grid[0].length;++i){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i = 1;i<grid.length;++i){
for(int j=1;j<grid[0].length;++j){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
- Method 2
/*
Optimize method 1:
Since dp[i][j] here is only related to dp[i-1][j] and dp[i][j-1], we can use the idea of rolling array to optimize the space complexity
1.Determine the subscript of dp array and its meaning
dp[j]Used to cache the current row
int[] dp = new int[n];
2.Determine recurrence formula
Since it can only move down or right, if you want to reach row i, you must come from the previous row (j-1) or the current row (j)
Then DP [J] = math min(dp[j],dp[j-1])+grid[i][j]
3.initialization
According to the recurrence formula, its basis is derived from dp[0]
So dp[0] = grid[0][0];
Cache first row
dp[i] = dp[i-1] + grid[0][i];
4.Determine traversal order
From the recursive formula, we can see that dp[j] is derived from dp[j-1] and dp[j], so it is a sequential traversal
5.final result
It can be seen that reaching the last position is the last value of the array, namely dp[n-1];
*/
class Solution {
public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
dp[0] = grid[0][0];
for(int i=1;i<grid[0].length;++i){
dp[i] = dp[i-1] + grid[0][i];
}
for(int i = 1;i<grid.length;++i){
dp[0] = dp[0] + grid[i][0];//Stores the first value of the current row
for(int j=1;j<grid[0].length;++j){
dp[j] = Math.min(dp[j],dp[j-1])+grid[i][j];
}
}
return dp[grid[0].length-1];
}
}
91. Decoding method
A message containing the letters A-Z is encoded by the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
To decode an encoded message, all numbers must be mapped back to letters based on the above mapping method (there may be several methods). For example, "11106" can be mapped as:
"AAJF", grouping messages into (1 1 10 6)
"KJF", grouping messages into (11 10 6)
Note that messages cannot be grouped into (1 11 06) because "06" cannot be mapped to "F", because "6" and "06" are not equivalent in the mapping.
To give you a non empty string s containing only numbers, please calculate and return the total number of decoding methods.
The question data ensures that the answer must be a 32-bit integer.
1 <= s.length <= 100
s contains only numbers and may contain leading zeros.
- Method 1
/*
1.Determine the meaning of dp array and its subscript
dp[i]Represents the total number of decoding methods for the first i characters of string s
int[] dp = new int[s.length()+1];
2.Determine recurrence formula
Since the number corresponding to the letter is 1 digit or 2 digits
When one character is used: dp[i] = dp[i-1] (of course, the ith character of the string cannot be '0')
When using two characters: dp[i] = dp[i-2] (because 0x cannot appear, the i-1 character of the string cannot be '0', and the number spliced by the two characters cannot be greater than 26, and I must be greater than 1)
The above two recursive transfer equations are accumulated when the corresponding conditions are met
3.initialization
Recursive formulas can be derived, and their basis is derived from dp[0]
Therefore dp[0] = 1; That is, an empty string can have a decoding method to decode an empty string.
4.Determine traversal order
It can be seen from the recursive formula that it is a sequential traversal
5.final result
dp[s.length()];
*/
class Solution {
public int numDecodings(String s) {
int[] dp = new int[s.length()+1];
dp[0] = 1;
for(int i=1;i<=s.length();++i){
if(s.charAt(i-1)!= '0'){
dp[i] += dp[i-1];
}
if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2)-'0')*10 + (s.charAt(i-1)-'0') <= 26)){
dp[i] += dp[i-2];
}
}
return dp[s.length()];
}
}
- Method 2
/*
Optimize method 1
Because dp[i] is only related to dp[i-1] and dp[i-2], three variables can be used for state transition and spatial optimization
Num0, num1 and num2 correspond to dp[i], dp[i-1] and dp[i-2] respectively
*/
class Solution {
public int numDecodings(String s) {
int num0;
int num1 = 1;
int num2 = 0;
for(int i=1;i<=s.length();++i){
num0 = 0;
if(s.charAt(i-1)!= '0'){
num0 += num1;
}
if(i>1 && s.charAt(i-2) != '0' && ((s.charAt(i-2)-'0')*10 + (s.charAt(i-1)-'0') <= 26)){
num0 += num2;
}
num2 = num1;
num1 = num0;
}
return num0;
}
}
120. Triangle minimum path and
Given a triangle, find the minimum path sum from top to bottom.
Each step can only move to the adjacent nodes in the next row. Adjacent nodes here refer to two nodes whose subscript is the same as or equal to the subscript + 1 of the previous node. That is, if it is in the subscript i of the current row, the next step can be moved to the subscript i or i + 1 of the next row.
1 <= triangle.length <= 200
triangle[0].length = 1
triangle[i].length = triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
- Method 1
/*
1.Determines the meaning of recursive arrays and their subscripts
dp[i][j]Represents the minimum path from the vertex to the position (i,j) and
int[][] dp = new int[n][n];
2.Determine recurrence formula
Since each step can only move to the next row of "adjacent nodes", if you want to go to position (i,j), the previous step can only be in position (i − 1,j − 1) or position (i − 1,j).
We choose one path and the smaller one in these two positions to transfer. The state transfer equation is
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + t[i][j]
t[i][j]A value representing the position of (i,j) in a triangle
Boundary conditions should also be considered
Left boundary dp[i][0] = dp[i-1][0] + t[i][0]
Right boundary dp[i][i] = dp[i − 1][i − 1] + t[i][i]
3.initialization
dp[0][0] = t[0][0];
4.traversal order
It can be seen from the recursive formula that it is a sequential traversal
5.final result
That is, the minimum value from dp[n-1][0] to dp[n-1][n-1], where n is the number of rows of the triangle
*/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n=triangle.size();
int[][] dp = new int[n][n];
dp[0][0] = triangle.get(0).get(0);
for(int i=1;i<n;++i){
dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
for(int j=1;j<i;++j){
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
}
dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
}
int ans = dp[n-1][0];
for(int i=1;i<n;++i){
ans = Math.min(ans,dp[n-1][i]);
}
return ans;
}
}
- Method 2
/*
Spatial optimization of method 1
According to the recurrence formula, dp[i] [..] Only with dp[i-1] [..] of
Therefore, we can store only the state of i-1 and the state of i
int[][] dp = new int[2][n];
*/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n=triangle.size();
int[][] dp = new int[2][n];
dp[0][0] = triangle.get(0).get(0);
for(int i=1;i<n;++i){
int cur = i%2;
int pre = 1-cur;
dp[cur][0] = dp[pre][0] + triangle.get(i).get(0);
for(int j=1;j<i;++j){
dp[cur][j] = Math.min(dp[pre][j-1], dp[pre][j]) + triangle.get(i).get(j);
}
dp[cur][i] = dp[pre][i-1] + triangle.get(i).get(i);
}
int ans = dp[(n - 1) % 2][0];
for(int i=1;i<n;++i){
ans = Math.min(ans,dp[(n - 1) % 2][i]);
}
return ans;
}
}
-Method 3
/*
Continue to optimize
Only record the status of the previous layer and change the value from back to front
int[] dp = new int[n]; Cache current row
*/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n=triangle.size();
int[] dp = new int[n];
dp[0] = triangle.get(0).get(0);
for(int i=1;i<n;++i){
//When j=i, it can only come up from the left
dp[i] = dp[i-1] + triangle.get(i).get(i);
for(int j=i-1;j>0;--j){
//The line elements come from the top left and top minimum values
dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
}
//The first element of the line can only be from the first element of the previous line
dp[0] = dp[0] + triangle.get(i).get(0);
}
int ans = dp[0];
for(int i=1;i<n;++i){
ans = Math.min(ans,dp[i]);
}
return ans;
}
}
139. Pronoun splitting
Given a non empty string s and a list wordDict containing non empty words, determine whether s can be split into one or more words in the dictionary by spaces.
explain:
Words in the dictionary can be reused when splitting.
You can assume that there are no duplicate words in the dictionary.
/*
1.Determine dp array and its subscript meaning
dp[i]Indicates whether the string composed of the first i characters of string s can be split into several words in the dictionary by spaces
int[] dp = new int[s.length()+1];
2.Determine recurrence formula
dp[i] = dp[j] && ((j,i)(is the word in the list)
3.initialization
You can use the hashset set to extract duplicate elements from the list
dp[0] = true;
4.Sequential traversal
5.final result
dp[s.length()]
*/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> wordSet = new HashSet<String>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i=1;i<=s.length();++i){
for(int j=0;j<=i-1;++j){
if(dp[j] && wordSet.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
198. House raiding
You are a professional thief who plans to steal houses along the street. There is a certain amount of cash hidden in each room. The only restrictive factor affecting your theft is that the adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are intruded by thieves on the same night, the system will automatically alarm.
Given a non negative integer array representing the amount stored in each house, calculate the maximum amount you can steal overnight without touching the alarm device.
1 <= nums.length <= 100
0 <= nums[i] <= 400
- Method 1
/*
1.Determine the subscript of dp array and its meaning
dp[i] Indicates the maximum total amount that can be stolen from the first i house
2.Recurrence formula
It can be seen that each room has two states of stealing or not stealing
When the i-th room is not stolen, the total amount of theft is the total amount of the first i-1 room
When stealing room i, room i-1 cannot be stolen. Therefore, the total amount of theft is the total amount of the first i-2 rooms plus the amount of room i
Then the maximum amount that can be stolen DP [i] = max (DP [I-1], d [I-2] + num [i]])
3.initialization
Considering boundary conditions
When there is only one room
dp[0] = nums[0];
When there are two rooms
dp[1] = max(nums[0],nums[1]);
4.Determine order
The recursive formula shows that it is a sequential traversal
5.final result
dp[nums.length-1];
*/
class Solution {
public int rob(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;++i){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
}
- Method 2
/*
Optimize method 1
It can be seen from the recursive formula dp[i] = max(dp[i-1],d[i-2]+nums[i]])
dp[i]It is only related to dp[i-1] and dp[i-2], so we can optimize the space with the idea of rolling array
*/
class Solution {
public int rob(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int one = nums[0];
int two = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;++i){
int temp = two;
two = Math.max(two,one+nums[i]);
one = temp;
}
return two;
}
}
213. House raiding II
You are a professional thief. You plan to steal houses along the street. There is a certain amount of cash in each room. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are intruded by thieves on the same night, the system will automatically alarm.
Given a non negative integer array representing the amount stored in each house, calculate the maximum amount you can steal tonight without touching the alarm device.
1 <= nums.length <= 100
0 <= nums[i] <= 1000
- Method 1
/*
This question is connected with the end of the house. We should consider the beginning and end of the house
Then the range we can steal becomes (0, num.length-2) or (1, num.length-1)
Each of these situations has become the situation in house raiding 1
*/
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if(length == 1){
return nums[0];
}else if(length == 2){
return Math.max(nums[0],nums[1]);
}
return Math.max(robRange(nums,0,length-2),robRange(nums,1,length-1));
}
public int robRange(int[] nums,int start,int end){
int[] dp = new int[nums.length-1];
dp[0] = nums[start];
dp[1] = Math.max(nums[start],nums[start+1]);
for(int i=2;i<nums.length-1;++i){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i+start]);
}
return dp[nums.length-2];
}
}
- Method 2
/*
Optimize method 1
*/
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if(length == 1){
return nums[0];
}else if(length == 2){
return Math.max(nums[0],nums[1]);
}
return Math.max(robRange(nums,0,length-2),robRange(nums,1,length-1));
}
public int robRange(int[] nums,int start,int end){
int one = nums[start];
int two = Math.max(nums[start],nums[start+1]);
for(int i = start+2;i<=end;++i){
int temp = two;
second = Math.max(one+nums[i],two);
one = temp;
}
return two;
}
}
221. Maximum square
In a two-dimensional matrix consisting of '0' and '1', find the largest square containing only '1' and return its area.
m = matrix.length
n = matrix[i].length
1 <= m, n <= 300
matrix[i][j] is' 0 'or' 1 '
Source: LeetCode
Link: https://leetcode-cn.com/problems/maximal-square
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
/*
1.Determine dp array and its subscript meaning
dp[i,j]Represents the maximum side length of a square with (i,j) as the lower right corner and containing only 1.
int[][] dp = new int[m][n];
2.Determine recurrence formula
If the value of the position is 0, dp(i,j)=0, because the current position cannot be in a square composed of 1;
If the value of this position is 1, the value of dp(i,j) is determined by the dp values of the three adjacent positions above, to the left and to the left. Specifically, the element value of the current position is equal to the minimum value of the elements of three adjacent positions plus 1
Then dp[i][j] = min(dp[i-1][j],dp[i],j-1],dp[i-1][j-1]) + 1;
maxSize = max(maxSize,dp[i][j])
3.initialization
Considering boundary conditions
If matrix[i][j] = '1'; dp[i][j]=1 when i=0 or j=0;
4.Sequential traversal
5.final result
maxSide*maxSide
*/
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int maxSide = 0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(matrix[i][j] == '1'){
if(i==0 || j==0){
dp[i][j] = 1;
}else{
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
}
}
maxSide = Math.max(maxSide,dp[i][j]);
}
}
return maxSide*maxSide;
}
}
1.1. 3 difficult topics
72. Edit distance
Here are two words word1 and word2. Please calculate the minimum operands used to convert word1 to word2.
You can perform the following three operations on a word:
Insert a character
Delete a character
Replace one character
0 <= word1.length, word2.length <= 500
word1 and word2 are composed of lowercase English letters
/*
1.Determine dp array subscript and its meaning
dp[i][j]Represents the minimum operation used to convert the first i letters of word1 to the first j letters of word2
int[] dp = new int[word1.length()+1][word2.length()+1];
2.Determine recurrence formula
If the current letters are the same, dp[i][j] = dp[i-1][j-1];
Otherwise, take the minimum value of the three operations + 1
3.initialization
dp[i][0] = i;dp[0][j] = j
4.traversal order
It can be seen from the recursive formula that it is a sequential traversal
5.final result
dp[word1.length()][word2.length()]
*/
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if(m*n == 0){
return m+n;
}
int[][] dp = new int[m+1][n+1];
for(int i=0;i<m+1;++i){
dp[i][0] = i;
}
for(int i=0;i<n+1;++i){
dp[0][i] = i;
}
for(int i=1;i<m+1;++i){
for(int j=1;j<n+1;++j){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
return dp[m][n];
}
}
85. Maximum rectangle
Given a two-dimensional binary matrix containing only 0 and 1 and the size of rows x cols, find the largest rectangle containing only 1 and return its area
rows = matrix.length
cols =matrix[0].length
0 <= row, cols <= 200
matrix[i][j] is' 0 'or' 1 '
/*
1.Determine the meaning of dp array and its subscript
dp[i][j]Represents the width when reaching the position (i,j)
int[][] dp = new int[m][n];
2.Determine recurrence formula
When matrix[i][j] == '1':
If j=0, dp[i][j] = 1;
Otherwise, it is the width when reaching the (i,j-1) position plus 1, that is, dp[i][j] = dp[i][j-1] + 1
When determining the height, we need to find it from bottom to top, and the rectangle that can be combined depends on the minimum width. The area of each rectangle is obtained in turn, and the maximum value is the final result
*/
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
if(m == 0){
return 0;
}
int n = matrix[0].length;
int[][] dp = new int[m][n];
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(matrix[i][j] == '1'){
dp[i][j] = (j==0 ? 0 : dp[i][j-1]) + 1;
}
}
}
int ret = 0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(matrix[i][j] == '0'){
continue;
}
int width = dp[i][j];
int area = width;
for(int k=i-1;k>=0;--k){
width = Math.min(width,dp[k][j]);
area = Math.max(area,(i-k+1)*width);
}
ret = Math.max(area,ret);
}
}
return ret;
}
}
145. Different subsequences
Given a string s and a string t, calculate the number of occurrences of T in the subsequence of S.
A subsequence of a string is a new string formed by deleting (or not deleting) some characters without interfering with the relative position of the remaining characters. (for example, "ACE" is a subsequence of "ABCDE" and "AEC" is not)
The question data ensures that the answer conforms to the range of 32-bit signed integers.
0 <= s.length, t.length <= 1000
s and t consist of English letters
/*
1.Determine the meaning of dp array and its subscript
dp[i][j]Represents the number of occurrences of the string composed of the first j characters of string t in the subsequence of the string composed of the first i characters of string s
int[][] dp = new int[m+1][n+1];
2.Determine recurrence formula
If the ith character of s is equal to the ith character of t, we can match with or without the ith character of s
Therefore, dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
If they are not equal, they cannot be matched with the ith character of s
So dp[i][j] = dp[i-1][j]
3.initialization
From the recurrence formula dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; And dp[i][j] = dp[i - 1][j]; It can be seen that dp[i][0] and dp[0][j] must be initialized.
dp[i][0] Indicates: s ending with the ith character can delete any element and the number of empty strings.
Then dp[i][0] must be 1, because that is, delete all elements of s ending with the ith character, and the number of empty strings is 1.
Let's look at dp[0][j], dp[0][j]: the empty string s can delete any element, and the number of string t ending with the j-th character appears.
Then dp[0][j] must all be 0, s can't become t anyway.
Finally, it depends on a special position, that is, how much dp[0][0] should be.
dp[0][0]It should be 1. The empty string s can delete 0 elements and become an empty string t.
4.traversal order
From the recurrence formula dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; And dp[i][j] = dp[i - 1][j];
It can be seen that dp[i][j] is pushed from the top left and right above.
Therefore, the traversal must be from top to bottom and from left to right, so as to ensure that dp[i][j] can be calculated according to the previously calculated values.
5.final result
dp[m][n];
*/
class Solution {
public int numDistinct(String s, String t) {
int m = s.length();
int n = t.length();
int[][] dp = new int[m+1][n+1];
for(int i=0;i<=m;++i){
dp[i][0] = 1;
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(s.charAt(i-1) == t.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[m][n];
}
}
123. The best time to buy and sell stocks III
Given an array, its ith element is the price of a given stock on day i.
Design an algorithm to calculate the maximum profit you can make. You can complete up to two transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
1 <= prices.length <= 105
0 <= prices[i] <= 105
- Method 1
/*
1.Determine the meaning of dp array and subscript
There are five states in a day,
No operation
First purchase
First sale
Second purchase
Second sale
dp[i][j]Where I represents day I, j is in [0 - 4] five states, and dp[i][j] represents the maximum cash left in state j on day I.
int[][] dp = new int[m][5];
2.Determine recurrence formula
If there is no operation on the i day, the status is the same as that of the previous day
dp[i][0] = dp[i-1][0]
Note: dp[i][1], * * indicates the status of buying stocks on day I, not that you must buy stocks on day I.
To reach dp[i][1] status, there are two specific operations:
Operation 1: if you buy stocks on day I, dp[i][1] = dp[i-1][0] - prices[i]
Operation 2: there is no operation on day I, but the buying status of the previous day is used, that is, dp[i][1] = dp[i - 1][1]
To maximize profits, dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
Similarly dp[i][2] there are two operations:
Operation 1: if the stock is sold on day I, dp[i][2] = dp[i - 1][1] + prices[i]
Operation 2: there is no operation on day I, and the status of selling stocks on the previous day is used, i.e. dp[i][2] = dp[i - 1][2]
So dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
Similarly, the remaining status can be deduced:
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
3.dp How to initialize an array
There is no operation on day 0. The easiest thing to think of is 0, that is, dp[0][0] = 0;
Do the first purchase on day 0, dp[0][1] = -prices[0];
What is the initial value of the first sale on day 0?
First of all, the operation of selling must be to gain profits. The worst case of the whole stock trading is that there is no profit, that is, the cash without operation in the whole process is 0,
It can be seen from the recurrence formula that the maximum value is taken every time. Since the profit is harvested, if it is smaller than 0, it is not necessary to harvest this profit.
So dp[0][2] = 0;
What should be the initial value of the second buying operation on day 0?
No matter how many times, there is no cash on hand now. As long as you buy, the cash will be reduced accordingly
Therefore, the second purchase operation is initialized as: dp[0][3] = -prices[0];
Similarly, the second selling initialization dp[0][4] = 0;
4.Determine traversal order
It can be seen from the recursive formula that it must traverse from front to back, because dp[i] depends on the value of dp[i - 1].
5.final result
dp[m-1][4]
*/
class Solution {
public int maxProfit(int[] prices) {
int m = prices.length;
int[][] dp = new int[m][5];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
for(int i=1;i<m;++i){
dp[i][0] = dp[i-1][0];
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
}
return dp[m-1][4];
}
}
- Method 2
/*
Optimize method 1
As can be seen from the recursive array, dp[i] [..] Only with dp[i-1] [..] For, use the scrolling array for optimization
int dp[] = new int[5];
*/
class Solution {
public int maxProfit(int[] prices) {
int m = prices.length;
int[] dp = new int[5];
dp[1] = -prices[0];
dp[3] = -prices[0];
for(int i=1;i<m;++i){
dp[1] = Math.max(dp[1], dp[0] - prices[i]);
dp[2] = Math.max(dp[2], dp[1] + prices[i]);
dp[3] = Math.max(dp[3], dp[2] - prices[i]);
dp[4] = Math.max(dp[4], dp[3] + prices[i]);
}
return dp[4];
}
}
- Method 3
/*
You can also optimize to constant space
*/
class Solution {
public int maxProfit(int[] prices) {
int m = prices.length;
int buyFirst = -prices[0];
int sellFirst = 0;
int buySecond = -prices[0];
int sellSecond = 0;
for(int i=1;i<prices.length;++i){
buyFirst = Math.max(buyFirst,-prices[i]);
sellFirst = Math.max(sellFirst, buyFirst + prices[i]);
buySecond = Math.max(buySecond , sellFirst - prices[i]);
sellSecond = Math.max(sellSecond, buySecond + prices[i]);
}
return sellSecond;
}
}
188. The best time to buy and sell stocks IV
Given an integer array prices, its ith element prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete up to k transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
- Method 1
/*
Promotion of III
1.Determine the meaning of dp array and its subscript
dp[i][j] : Indicates that the status on day I is j, and the maximum cash left is dp[i][j]
j The status of is expressed as:
0 Indicates no operation
1 First purchase
2 First sale
3 Second purchase
4 Second sale
.....
It can be seen that in addition to 0, even numbers are selling and odd numbers are buying.
The topic requires that there are at most K transactions, so the range of j is defined as 2 * k + 1.
int[][] dp = new int[m][2 * k + 1];
2.Determine recurrence formula
To reach dp[i][1] status, there are two specific operations:
Operation 1: if you buy stocks on day I, dp[i][1] = dp[i - 1][0] - prices[i]
Operation 2: there is no operation on day I, but the buying status of the previous day is used, that is, dp[i][1] = dp[i - 1][1]
Select the largest, so dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][0]);
Similarly dp[i][2] there are two operations:
Operation 1: if the stock is sold on day I, dp[i][2] = dp[i - 1][1] + prices[i]
Operation 2: there is no operation on day I, and the status of selling stocks on the previous day is used, i.e. dp[i][2] = dp[i - 1][2]
So dp[i][2] = max(dp[i - 1][i] + prices[i], dp[i][2])
Similarly
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]); //Odd case
dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);//Even case
3.initialization
There is no operation on day 0. The easiest thing to think of is 0, that is, dp[0][0] = 0;
Do the first purchase on day 0, dp[0][1] = -prices[0];
What is the initial value of the first sale on day 0?
First of all, the operation of selling must be to gain profits. The worst case of the whole stock trading is that there is no profit, that is, the cash without operation in the whole process is 0,
It can be seen from the recurrence formula that the maximum value is taken every time. Since the profit is harvested, if it is smaller than 0, it is not necessary to harvest this profit.
So dp[0][2] = 0;
What should be the initial value of the second buying operation on day 0?
No matter how many times, there is no cash on hand now. As long as you buy, the cash will be reduced accordingly
Therefore, the second purchase operation is initialized as: dp[0][3] = -prices[0];
Similarly, the second selling initialization dp[0][4] = 0;
....
It can be deduced that when j is an odd number, the initial value is - prices[0]; 0 for even numbers
4.Determine traversal order
It can be seen from the recursive formula that it must traverse from front to back, because dp[i] depends on the value of dp[i - 1].
5.final result
The last sale must be the one with the largest profit. dp[m-1][2 * k] is the final solution.
*/
class Solution {
public int maxProfit(int k, int[] prices) {
//The length of the array in this question can be 0, so we should consider the case of 0
if(prices.length == 0){
return 0;
}
int m = prices.length;
int[][] dp = new int[m][2*k+1];
for(int j=1;j<2*k;j+=2){
dp[0][j] = -prices[0];
}
for(int i=1;i<m;++i){
for(int j=1;j<2*k;j+=2){
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
}
}
return dp[m-1][2*k];
}
}
- Method 2
/*
Optimization of method 1
*/
class Solution {
public int maxProfit(int k, int[] prices) {
//The length of the array in this question can be 0, so we should consider the case of 0
if(prices.length == 0){
return 0;
}
int m = prices.length;
int[] dp = new int[2*k+1];
for(int j=1;j<2*k;j+=2){
dp[j] = -prices[0];
}
for(int i=1;i<m;++i){
for(int j=1;j<2*k;j+=2){
dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
dp[j+1] = Math.max(dp[j+1], dp[j] + prices[i]);
}
}
return dp[2*k];
}
}