Shulou(Shulou.com)06/01 Report--

In this article Xiaobian for you to introduce in detail the "C language dp algorithm LeetCode stock speculation exercise case analysis", the content is detailed, the steps are clear, the details are handled properly, I hope this "C language dp algorithm LeetCode stock speculation exercise case analysis" article can help you solve doubts, following the editor's ideas slowly in-depth, together to learn new knowledge.

Concept

When it comes to dynamic planning, what is dynamic planning?

Dynamic programming (English: Dynamic programming, referred to as dp) is a method of solving complex problems by decomposing the original problem into relatively simple sub-problems. Dynamic programming is often suitable for problems with overlapping subproblems and optimal substructure properties.

It looks so complicated, ha, in fact, it is summed up that major matters are reduced to small ones and split into small problems, but these small problems are homogeneous with the original problem. Dynamic rules are committed to solving each sub-problem, reducing computation, in fact, it is somewhat similar to recursive thinking and the divide-and-conquer method. Fibonacci series can be regarded as an entry-level classical dynamic problem.

Here is a popular example on the Internet to give you a taste:

A: "1-1-1-1-1-1-1-1-1-1 =?"

A: "what is the value of the above equation?"

B: calculate "8"

A: write "1 +" on the left side of the above equation?

A: "what is the value of the equation at this time?"

B: get the answer "9" very quickly

A: "how did you know the answer so quickly?"

A: "just add one to eight."

A: "so you don't have to recalculate, because you remember that the value of the first equation is 8! dynamic programming algorithm can also be said to 'remember the solution to save time'."

Nature

1. Optimization principle: if the solution of the subproblem contained in the optimal solution of the problem is also optimal, it is said that the problem has the optimal substructure, that is, it satisfies the optimization principle.

two。 There are overlapping sub-problems: that is, the sub-problems are not independent, and one sub-problem may be used many times in the next stage of decision-making.

3. No aftereffect: that is, once the state of a certain stage is determined, it will not be affected by future decisions in this state. In other words, the process after a certain state will not affect the previous state, but only related to the current state (to say human words is to turn water into ice, but it is still water in essence)

Typical characteristics

Dynamic programming has four typical characteristics:

1. Optimal substructure

two。 State transfer equation

3. Boundary

4. Overlapping subproblem

Take the Fibonacci number we are familiar with as an example

The optimal substructure of f (n) is called the optimal substructure of f (n), f (n) = f (nmur1) + f (nmur2) is called the state transition equation, f (1) = 1, f (2) = 2 is called the boundary, where f (5) = f (4) + f (3), f (4) = f (3) + f (2), f (3) is the overlapping subproblem.

Actual combat demonstration

If we want to learn the dp algorithm, we must talk about the nose problem in LeetCode-- a series of stock speculation problems. Let's take an example to understand its typical characteristics when we come to Hong Kong.

The initial question is relatively simple. Let's take II as an example:

Example:

Input: prices = [7, 1, 5, 3, 6, 4]

Output: 7

Small shortcut

See here in fact the simplest way has been clear, that is greedy algorithm, as long as you can make a profit, as long as I do not lose money, I will buy! Do you think I am greedy or not?

Int maxProfit (int* prices, int pricesSize) {int sum = 0; for (int I = 1; I)

< pricesSize; ++i) { sum += fmax(0, prices[i] - prices[i - 1]); } return sum;} 这里用了一个库函数 fmax ，需要引头文件，用于比较两个参数的最大值，语法是： type fmax (参数1 , 参数2); 再介绍一种我自己用的方法，和贪心原理上差不多，只是用的普普通通的遍历： int maxProfit(int* prices, int pricesSize) { int n = 0; if (pricesSize == 0) { return 0; } int sum = 0; while (n < pricesSize - 1) { for (n = 0; n < pricesSize - 1; n++) if (prices[n + 1] - prices[n] >

0) / / make sure you can make money by buying and selling {sum + = prices [n + 1]-prices [n];}} return sum;}

My own method is better.

In this way, we can take it away in one set, but we have to use dp to take care of him. Dp is actually very simple, but it looks a little complicated, so we can't be deterred from it.

According to the analysis of the conditions, it is said in the title that we cannot buy and sell many times, then we have and only have one, that is, we do not have one, that is, we have zero in our hands, and there are two other possibilities, that is, the previous day was zero and there was one on this day, but it was sold; by the same token, in the case of one, we had one empty-handed the day before, but I bought one today. Based on this, we write the state transition equation for the maximum profit (I starting from 0):

On the first day, there are 0 stocks: dp [I] [0] = DP [I-1] [0] + dp [I] [1] + prices [I]; on the first day, there is a stock: dp [I] [1] = DP [I-1] [1] + DP [I-1] [0]-prices [I]

When the state transfer equation is written, the problem is easily solved.

Algorithm realization

1. Save the results of each sub-problem with the help of an array or a two-dimensional array. Whether to create an array or a two-dimensional array depends on the topic, such as the number of change of different denominations and total money in the change problem, so you need to create a two-dimensional array.

2. corresponding to the dry condition of the question, the specific requirements are to set the boundary value of the array. One-dimensional array is to set the first number, and two-dimensional array is to set the value of the first row and the first column.

3. Find out the state transition equation, find the relationship between each state and its last state, and write the code according to the state transformation equation.

We can write the entire code framework using the state transition equation we have just deduced:

Int maxProfit (int* prices, int pricesSize) {int sz = pricesSize; int item0; int dp [sz] [2] = 0; / sz is the price within the maximum number of trading days, 2 represents the two states 0 and 1 dp [0] [0] = 0dp [0] [1] =-prices [0]; / / sets the boundary value for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.