[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.
Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card
What problem can I choose to do dynamic programming?
Counting 1.
- How many ways can I get to the bottom right corner
- How many ways can I pick the sum of k numbers yes is sum
2. Find the maximum and minimum
- The maximum numeric sum of the path from the upper left corner to the lower right corner
- Maximum ascending subsequence length
3. Seek existence
- Stone game, whether the first hand will win
- Can we pick k numbers such that the sum is sum
4. Comprehensive application
- Dynamic planning + hash
- Dynamic programming + recursion
- .
Leecode 188. The best time to buy and sell stocks IV
Given an array of integers 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 do k transactions at most.
Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: If you buy on day 1 (stock price = 2) and sell on day 2 (stock price = 4), the exchange makes a profit of 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: If you buy on day 2 (stock price = 2) and sell on day 3 (stock price = 6), the exchange will make a profit = 6-2 = 4.
Then, by buying on day 5 (stock price = 0) and selling on day 6 (stock price = 3), the exchange makes a profit = 3-0 = 3.
Tip:
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
—
Reference code
The language version
func maxProfit(k int, prices []int) int {
n := len(prices)
if n == 0 {
return 0
}
k = min(k, n/2)
buy := make([] []int, n)
sell := make([] []int, n)
for i := range buy {
buy[i] = make([]int, k+1)
sell[i] = make([]int, k+1)
}
buy[0] [0] = -prices[0]
for i := 1; i <= k; i++ {
buy[0][i] = math.MinInt64 / 2
sell[0][i] = math.MinInt64 / 2
}
for i := 1; i < n; i++ {
buy[i][0] = max(buy[i- 1] [0], sell[i- 1] [0]-prices[i])
for j := 1; j <= k; j++ {
buy[i][j] = max(buy[i- 1][j], sell[i- 1][j]-prices[i])
sell[i][j] = max(sell[i- 1][j], buy[i- 1][j- 1]+prices[i])
}
}
return max(sell[n- 1]...). }func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}
Copy the code
Java version
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2);
int[][] buy = new int[n][k + 1];
int[][] sell = new int[n][k + 1];
buy[0] [0] = -prices[0];
sell[0] [0] = 0;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) {
buy[i][0] = Math.max(buy[i - 1] [0], sell[i - 1] [0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]); }}return Arrays.stream(sell[n - 1]).max().getAsInt(); }}Copy the codeScrolling arrays at it again!!
Buy [I][j] and sell[I][j] both from buy[I −1][..] And sell [I – 1] [..] Transfer to
B [j] please Max {b [j], s [j] – price [I]}
S [j] please Max {s [j], [j – 1) + b price [I]}
The language version
func maxProfit(k int, prices []int) int { n := len(prices) if n == 0 { return 0 } k = min(k, n/2) buy := make([]int, k+1) sell := make([]int, k+1) buy[0] = -prices[0] for i := 1; i <= k; i++ { buy[i] = math.MinInt64 / 2 sell[i] = math.MinInt64 / 2 } for i := 1; i < n; i++ { buy[0] = max(buy[0], sell[0]-prices[i]) for j := 1; j <= k; j++ { buy[j] = max(buy[j], sell[j]-prices[i]) sell[j] = max(sell[j], buy[j-1]+prices[i]) } } return max(sell...) } func min(a, b int) int { if a < b { return a } return b } func max(a ... int) int { res := a[0] for _, v := range a[1:] { if v > res { res = v } } return res }Copy the codeJava version
class Solution { public int maxProfit(int k, int[] prices) { if (prices.length == 0) { return 0; } int n = prices.length; k = Math.min(k, n / 2); int[] buy = new int[k + 1]; int[] sell = new int[k + 1]; buy[0] = -prices[0]; sell[0] = 0; for (int i = 1; i <= k; ++i) { buy[i] = sell[i] = Integer.MIN_VALUE / 2; } for (int i = 1; i < n; ++i) { buy[0] = Math.max(buy[0], sell[0] - prices[i]); for (int j = 1; j <= k; ++j) { buy[j] = Math.max(buy[j], sell[j] - prices[i]); sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]); } } return Arrays.stream(sell).max().getAsInt(); }}Copy the code❤ ️ ❤ ️ ❤ ️ ❤ ️
Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!
If there are any mistakes in this blog, please comment, thank you very much!
At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.