Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1c20a18

Browse files
committed
浅谈什么是动态规划以及相关的「股票」算法题
1 parentd207212 commit1c20a18

File tree

3 files changed

+50
-43
lines changed

3 files changed

+50
-43
lines changed

‎notes/LeetCode第121号问题：买卖股票的最佳时机.md‎

Lines changed: 12 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,27 @@
22

33
#浅谈什么是动态规划以及相关的「股票」算法题
44

5+
>本文首发于公众号「五分钟学算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
6+
>
7+
>个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
8+
59
##动态规划
610

711
###1 概念
812

913
  **动态规划**算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。在学习动态规划之前需要明确掌握几个重要概念。
1014

11-
  **阶段：**对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
15+
  **阶段**：对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
1216

13-
  **状态：**状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
17+
  **状态**：状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
1418

15-
  **决策：**决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
19+
  **决策**：决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
1620

17-
  **策略：**由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
21+
  **策略**：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
1822

19-
  **最优策略：**在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
23+
  **最优策略**：在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
2024

21-
  **状态转移方程：**状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
25+
  **状态转移方程**：状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
2226

2327
###2 使用场景
2428

@@ -134,7 +138,7 @@ class Solution {
134138

135139
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
136140

137-
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
141+
**注意**：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
138142

139143
**示例 1:**
140144

@@ -286,7 +290,4 @@ class Solution {
286290

287291

288292

289-
###
290-
291-
292-
293+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎notes/LeetCode第122号问题：买卖股票的最佳时机II.md‎

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,27 @@
22

33
#浅谈什么是动态规划以及相关的「股票」算法题
44

5+
>本文首发于公众号「五分钟学算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
6+
>
7+
>个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
8+
59
##动态规划
610

711
###1 概念
812

913
  **动态规划**算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。在学习动态规划之前需要明确掌握几个重要概念。
1014

11-
  **阶段：**对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
15+
  **阶段**：对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
1216

13-
  **状态：**状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
17+
  **状态**：状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
1418

15-
  **决策：**决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
19+
  **决策**：决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
1620

17-
  **策略：**由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
21+
  **策略**：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
1822

19-
  **最优策略：**在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
23+
  **最优策略**：在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
2024

21-
  **状态转移方程：**状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
25+
  **状态转移方程**：状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
2226

2327
###2 使用场景
2428

@@ -97,14 +101,14 @@
97101

98102
所以我们只要考虑当天买和之前买哪个收益更高，当天卖和之前卖哪个收益更高。
99103

100-
* buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
101-
* sell = max(sell, prices[i] + buy)
104+
- buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
105+
- sell = max(sell, prices[i] + buy)
102106

103107
####边界
104108

105109
第一天`buy = -prices[0]`,`sell = 0`，最后返回 sell 即可。
106110

107-
###代码实现
111+
###代码实现
108112

109113
```java
110114
classSolution {
@@ -134,7 +138,7 @@ class Solution {
134138

135139
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
136140

137-
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
141+
**注意**：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
138142

139143
**示例 1:**
140144

@@ -257,11 +261,10 @@ class Solution {
257261

258262
####边界
259263

260-
* 一开始`fstBuy = -prices[0]`
261-
262-
* 买入后直接卖出，`fstSell = 0`
263-
* 买入后再卖出再买入，`secBuy - prices[0]`
264-
* 买入后再卖出再买入再卖出，`secSell = 0`
264+
- 一开始`fstBuy = -prices[0]`
265+
- 买入后直接卖出，`fstSell = 0`
266+
- 买入后再卖出再买入，`secBuy - prices[0]`
267+
- 买入后再卖出再买入再卖出，`secSell = 0`
265268

266269
最后返回 secSell 。
267270

@@ -286,7 +289,7 @@ class Solution {
286289

287290

288291

289-
###
292+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)
290293

291294

292295

‎notes/LeetCode第123号问题：买卖股票的最佳时机III.md‎

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,27 @@
22

33
#浅谈什么是动态规划以及相关的「股票」算法题
44

5+
>本文首发于公众号「五分钟学算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
6+
>
7+
>个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
8+
59
##动态规划
610

711
###1 概念
812

913
  **动态规划**算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。在学习动态规划之前需要明确掌握几个重要概念。
1014

11-
  **阶段：**对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
15+
  **阶段**：对于一个完整的问题过程，适当的切分为若干个相互联系的子问题，每次在求解一个子问题，则对应一个阶段，整个问题的求解转化为按照阶段次序去求解。
1216

13-
  **状态：**状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
17+
  **状态**：状态表示每个阶段开始时所处的客观条件，即在求解子问题时的已知条件。状态描述了研究的问题过程中的状况。
1418

15-
  **决策：**决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
19+
  **决策**：决策表示当求解过程处于某一阶段的某一状态时，可以根据当前条件作出不同的选择，从而确定下一个阶段的状态，这种选择称为决策。
1620

17-
  **策略：**由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
21+
  **策略**：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。
1822

19-
  **最优策略：**在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
23+
  **最优策略**：在所有的策略中，找到代价最小，性能最优的策略，此策略称为最优策略。
2024

21-
  **状态转移方程：**状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
25+
  **状态转移方程**：状态转移方程是确定两个相邻阶段状态的演变过程，描述了状态之间是如何演变的。
2226

2327
###2 使用场景
2428

@@ -97,14 +101,14 @@
97101

98102
所以我们只要考虑当天买和之前买哪个收益更高，当天卖和之前卖哪个收益更高。
99103

100-
* buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
101-
* sell = max(sell, prices[i] + buy)
104+
- buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
105+
- sell = max(sell, prices[i] + buy)
102106

103107
####边界
104108

105109
第一天`buy = -prices[0]`,`sell = 0`，最后返回 sell 即可。
106110

107-
###代码实现
111+
###代码实现
108112

109113
```java
110114
classSolution {
@@ -134,7 +138,7 @@ class Solution {
134138

135139
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
136140

137-
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
141+
**注意**：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
138142

139143
**示例 1:**
140144

@@ -257,11 +261,10 @@ class Solution {
257261

258262
####边界
259263

260-
* 一开始`fstBuy = -prices[0]`
261-
262-
* 买入后直接卖出，`fstSell = 0`
263-
* 买入后再卖出再买入，`secBuy - prices[0]`
264-
* 买入后再卖出再买入再卖出，`secSell = 0`
264+
- 一开始`fstBuy = -prices[0]`
265+
- 买入后直接卖出，`fstSell = 0`
266+
- 买入后再卖出再买入，`secBuy - prices[0]`
267+
- 买入后再卖出再买入再卖出，`secSell = 0`
265268

266269
最后返回 secSell 。
267270

@@ -286,7 +289,7 @@ class Solution {
286289

287290

288291

289-
###
292+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)
290293

291294

292295

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp