始于
分类：Algorithms
Tags: [ Algorithms ]
差劲的算法学习系列, 一维动态规划
差劲的算法学习 - 线性动态规划
序
一维动态规划这里有一些比较典型的题目, 比如LIS(最长不下降子序列, 最长上升子序列), 回文串搜索, 以及等下要提到的那道杭电题.
选择动态规划(Dynamic Programming, 下简称dp)的场合, 通常是题面中出现”最大”,”最小”,”最长”之类的时候. 我们将在之后的例子中验证这一点.
和最大子序列
这个问题其实并不需要用dp来做, 因为很容易就能想到其实只需要把序列中所有的正数和0加起来就行了; 如果序列中全为负数, 那就找到那个最大的负数. 这里, 我们将通过dp来验证这一点.
动态规划的思想是迭代, 在完成第n-1步的基础上应该如何完成第n步. 这种看起来有点像递归, 其实迭代不也就是尾递归嘛.
在这个问题中, 我们开两个数组, 一个用来存原始数据, 一个用来存分段和.
vector<int> arr;
vector<int> sums;
sums[i]用来表示arr[0...i]这段对于题面问题的解. 类似于数学归纳法, 我们只需要找到初始情况, 并通过sums[i]来推出sums[i + 1]等于多少, 整个问题也就能轻松解决了.
下面直接结合代码来说明整个思路:
这里模拟的情形是ACM模式的输入输出: 输入一个n, 后面跟着n个树, 存入数据数组.
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main()
{
int n;
while (cin >> n) {
vector<int> arr(n, 0);
vector<int> sums(n + 1, 0); // sums[i] = sum of arr[0...i - 1]
int m = numeric_limits<int>::min();
for (int i = 0; i < n; ++i) {
cin >> arr[i];
m = max(m, arr[i]);
}
if (m <= 0) {
cout << m << endl;
continue;
}
sums[0] = 0; // The initial condition
for (int i = 1; i <= n; ++i) {
sums[i] = max(sums[i - 1], sums[i - 1] + arr[i - 1]); // HERE
}
cout << sums[n] << endl; // output sums[n - 1]: sum of arr[0..n]
}
return 0;
}
其他的部分刚才都已经解释清楚了, 唯一一个含糊不清的地方, 即通过sums[i]来推出sums[i + 1]等于多少, 这里通过代码来说明.
在标有HERE注释的那一行代码sums[i] = max(sums[i - 1], sums[i - 1] + arr[i - 1]);, 这个被叫做状态转移方程, 为什么要叫方程不是很清楚, 但是为什么是状态转移, 是非常容易理解的.
百度百科给出了比较详细的定义和说明, 这里截取了一小段:
状态转移方程，是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第K阶段的状态$S_k$以及决策$u_k(S_k)$，则第$K+1$阶段的状态$S_{k+1}$也就完全确定。
我看这玩意儿反正越看越像数学归纳法. 同样, 这里在我的博客里截取了一段实分析习题证明:
P21 - 证明两个自然数的和仍旧是自然数.
题设: 两个自然数$n,m$.
求证: $n+m$仍为自然数.
证明:
固定$m$.
1) 当$n=0$时
由公理$2.1$可知, $0$是自然数
$n+m=0+m=m$为自然数 (加法定义)
2) 假设$n+m$是自然数
下证$(n++)+m$是自然数
$(n++)+m=(n+m)++$ (加法定义)
$\because n+m$为自然数 (假设)
$\therefore (n+m)++也为自然数$ (公理$2.2$)
综上归纳递归, 原题得证. $\square$
(完 全 一 致)
类比数学归纳法证明, 刚才大代码中注释The initial condition的部分对应数学归纳法中的1)情形, 之后循环里的状态转移方程对应的是数学归纳法中2)情形.
LIS, Longest Increasing Subsequence, 最长上升子序列(或最长不下降子序列)
下面举的例子不是LIS, 但是是差不多的东西, 于是就假装它是LIS了.
这部分搞过来的题目是杭电上一道模板题.
link here
Problem Description
Given a sequence a[1], a[2], a[3] … a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T (1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N (1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4Case 2:
7 1 6
不多说了, 直接上代码:
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main()
{
int t;
while (cin >> t){
for (int z = 0; z < t; ++z) {
if (z != 0) {
cout << endl;
}
int n;
cin >> n;
vector<int> lst(n, 0);
vector<int> dp(n + 1, numeric_limits<int>::min());
for (auto& rf: lst) {
cin >> rf;
}
int lo, st, ed, sum;
lo = st = ed = sum = 0;
for (int i = 0; i < n; ++i) {
sum += lst[i];
if (dp[i] >= sum) {
dp[i + 1] = dp[i];
} else {
dp[i + 1] = sum;
st = lo;
ed = i;
}
if (sum < 0) {
sum = 0;
lo = i + 1;
}
}
cout << "Case " << z + 1 << ":\n"
<< dp[n] << ' ' << st + 1 << ' ' << ed + 1 << endl;
}
}
return 0;
}
其实我这里写的代码已经不是很像dp了, 并且其实这一题都不用存储输入的数组.
稍微修改一下代码, 看一下dp数组里存了什么.
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
int t;
while (cin >> t){
for (int z = 0; z < t; ++z) {
int n;
cin >> n;
vector<int> lst(n, 0);
vector<int> dp(n + 1, numeric_limits<int>::min());
for (auto& rf: lst) {
cin >> rf;
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += lst[i];
if (dp[i] >= sum) {
dp[i + 1] = dp[i];
} else {
dp[i + 1] = sum;
}
if (sum < 0) {
sum = 0;
}
}
copy(dp.begin(), dp.end(), ostream_iterator<int>(cout, ", "));
cout << endl;
}
}
return 0;
}
Input:
Same as sample.
Output:
-2147483648, 6, 6, 10, 14, 14,
-2147483648, 0, 6, 6, 6, 6, 7, 7,
整个dp序列呈上升趋势, 这也是必然的, 因为越往后才会出现比之前更大的.
HDUOJ 1024. Max Sum Plus Plus
Problem Description
Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence $S_1, S_2, S_3, S_4 … S_x, … S_n (1 \le x \le n \le 1,000,000, -32768 \le S_x \le 32767)$. We define a function $sum(i, j) = S_i + … + S_j (1 \le i \le j \le n)$.
Now given an integer $m (m > 0)$, your task is to find $m$ pairs of $i$ and $j$ which make $sum(i_1, j_1) + sum(i_2, j_2) + sum(i_3, j_3) + … + sum(i_m, j_m)$ maximal ($i_x \le i_y \le j_x$ or $i_x \le j_y \le j_x$ is not allowed).
But I'm lazy, I don’t want to write a special-judge module, so you don’t have to output $m$ pairs of $i$ and $j$, just output the maximal summation of $sum(i_x, j_x)(1 \le x \le m)$ instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers $S_1$, $S_2$, $S_3 \cdots S_n$.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8Hint
Huge input, scanf and dynamic programming is recommended.