3 动态规划(Dynamic Programming)

3.1 算法介绍

3.1.1 动态规划特性

  • 问题分阶段：一个问题的求解可以拆分成若干个阶段的子问题
  • 阶段有依赖：问题的最优解依赖于子阶段问题的最优解
  • 问题有重复：一个问题的求解过程中，其子问题可能会重复出现

3.1.2 表格法

特点 适用情形 方向
求出所有解 要求所有解的情形 自下而上

3.1.3 备忘录法

特点 适用情形 方向 实现方法
只求出所需解 无需求出所有解的情况 自上而下 递归

3.2 最大子串和(Maximum Subarray)

3.2.1 问题描述

假设已知未来几天的股票市场价格，规定在这期间只能买卖一次，请问何时买卖才能使获利最大？

3.2.2 算法思路

整体思路：假设只有前两天可以买卖，算出一个最大收益，然后继续假设前三天可以买卖，算出最大收益……一直算到最后一天，就算出了我们最终的最大收益。

详细思路：
首先看如下这张表，其含义是：

  • 第一行表示当天价格和前一天价格的差价
  • 第二行表示当前累计的收益，如果小于0时，则归零。起到辅助第三行的作用
  • 第三行表示最大收益，也就是我们要求的答案

问题分阶段：第一列表示，假如只有前两天有买卖机会，最大收益是多少？第二列表示，假如只有前三天的有机会……
阶段有依赖：每一次算出的答案都可以依赖于前一次的答案，因此避开了许多重复操作。所谓的依赖，从这张表来看，就是最大收益[i]=max(当前累积[i],最大收益[i-1]),(i>0)
注意：这里只是为了方便说明，本文的代码中并没有用数组实现，而是直接使用了一个变量进行存储

我们需要做的，就是求出这张表。

3.2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int[] getByDynamicProgramming(int[] prices) {
		int[] changes = new int [prices.length-1];
		for(int i=0; i<changes.length;i++) {
			changes[i] = prices[i+1]-prices[i];
		}
		int maxSum = changes[0];
		int currentMaxSum = changes[0];
		int startIndex =0,endIndex =0;
		for(int currentIndex=1; currentIndex<changes.length; currentIndex++) {
		/*核心代码*/
			if(currentMaxSum<=0) {//如果累积小于零
				currentMaxSum = changes [currentIndex];//把当前累计设置为价格变化
				currentStartIndex = currentIndex;//暂时保存，直到最大收益值变化，再将其赋值给买入时间
			}
			else {
				currentMaxSum += changes[currentIndex];
			}
			if(currentMaxSum>maxSum) {//如果当前累积大于最大收益
				maxSum = currentMaxSum;//把当前累积赋值给最大收益
				startIndex = currentStartIndex;
				endIndex = currentIndex;//设置为这一天买入
			}
		}
		int [] answer = {maxSum, startIndex, endIndex+1};
		return answer;
	}

3.2.4 算法复杂度

Θ(n)