0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 五大经典算法之动态规划

动态规划，又名DP算法（取自其Dynamic Programming的缩写），最初是运筹学的一个分支，是用来求解决策过程最优化的数学方法。

1. 利用动态规划思想从上往下思考问题：将多阶段问题转变成更小的多阶段问题（状态转移方程）

2. 分解至最小的单阶段问题（可直接解决问题）。

3. 利用循环从下往上解决问题。

res：存储各阶段问题的答案

n：最终问题的标记位

i：循环的索引

f：某阶段问题的答案与前些阶段问题答案之间的函数关系

void dp(int n) {

// 定义问题的解数组

int res[n + 1];

// 初始化最小的单阶段问题的解

res[1] = 1 ...

// 从初始化后的解数组的第一个位置开始循环计算res[i]

int i = inital;

while (i <= n) {

// f函数取决于状态转移方程

res[i] = f(res[i - 1], res[i - 2], res[i - 3]...);

i++;

}

return res[n];

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

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

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2: Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

int maxProfit(int* prices, int pricesSize) {

if (pricesSize == 0) {

return 0;

}

int res[pricesSize];

int min[pricesSize];

res[0] = 0;

min[0] = prices[0];

int i = 1;

while (i < pricesSize) {

if (res[i - 1] < prices[i] - min[i - 1]) {

res[i] = prices[i] - min[i - 1];

} else {

res[i] = res[i - 1];

}

if (prices[i] < min[i - 1]) {

min[i] = prices[i];

} else {

min[i] = min[i - 1];

}

i++;

}

return res[pricesSize - 1];

}

+ 关注