动态规划的启蒙题目
题目：Pku 1163 the Triangle http://acm.pku.edu.cn/JudgeOnline/problem?id=1163
HDU 2084 数塔 http://acm.hdu.edu.cn/showproblem.php?pid=2084
对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如：
这个是经典的动态规划，也是最基础、最简单的动态规划，典型的多段图。思路就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值
核心代码：(c语言)
for (i=n-2;i>=0;i--)
{
for (j=0;j<=i;j++)
{
a[i][j] += a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
}
}
本题的详细完整代码请浏览：
http://blog.csdn.net/jqandjq/archive/2009/02/26/3938367.aspx
此题的特点是可以用递归的方法，但那为了避免重复地搜索，往往会运用“记录递归”的方法，那是一种自顶向下的过程，而DP的方法则相反，是一种自底向上逐步保存过程，用数组保存模拟。
由此我们可以推广出一种DP用“记录递归”的方法来完成：
Pku 1579 Function Run Fun http://acm.pku.edu.cn/JudgeOnline/problem?id=1579
Hdu 1579 Function Run Fun http://acm.hdu.edu.cn/showproblem.php?pid=1579
这本身就是一个递归函数，要是按照函数本身写递归式，结果肯定是TLE，这里我开了一个三维数组，从w(0,0,0)开始递推，逐步产生到w(20,20,20)的值，复杂度O(n^3).
总结：这道题是很地道的DP，因为它的子问题实在是太多了，所以将问题的结果保存起来，刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上的递推，这个例子就非常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。
本题的详细完整代码请浏览：
http://blog.csdn.net/jqandjq/archive/2009/02/26/3938504.aspx
接下来的介绍有关于动态规划的几种基础类型：
1．求序列的连续最大段 à 推广类型：求矩阵的最大子矩阵
2．求序列的最大上升序列
3．求序列的最大连续上升子序列
求序列的连续最大段：
典型例题：Max Sum：http://acm.hdu.edu.cn/showproblem.php?pid=1003
这是DP的经典之一，欲求出一个最优的结果，但不暴力地去枚举。
如一个序列：6,-1,5,4,-7 求它的连续最大段就是：6 + (-1) + 5 + 4 = 14.
用DP的方法只要一重的循环就可以把这道题搞定：
每一次的计算对前一次结果不会有影响，这是DP的特点。
这样之要从第一个开始计算，6 -1 5 4 -7 的最大值分别是 6 5 10 14 7
如果计算过程中值出现小于零的情况那就将值归零。
核心C代码：
int sum=0,maxnum=-1001,first =0, last = 0, temp = 1;
for (i=0;i<n;i++)
{
sum += a[i];
if (sum > maxnum)
{
maxnum = sum;first = temp;last = i+1;
}
if (sum < 0)
{
sum = 0;temp = i+2;
}
}
本题的详细完整代码请浏览：
http://blog.csdn.net/jqandjq/archive/2009/02/26/3940608.aspx
问题描述：
有n个数（以下都视为整数），每个数有正有负，现在要在n个数中选取相邻的一段，使其和最大，输出最大的和。
问题分析：
看到这个问题，它是属于带“最”字的问题，其实就是一个求最优解的问题。对于这种问题的朴素算法就是枚举出每种可能，然后在其中寻找一个最优的解，然后输出。因为输出仅要求这个子段的和，因此不必再记录关于解的组成的信息。
朴素算法是用i和j表示序列i到j的子段，然后判断这个子段的和是否是最大的，是就记录。然后用k求i到j之间的和，因此是O(n^3)的算法。
int LSS_SlowEnumerate(int a[]) //最大子段和，枚举算法，O(n^3){int max = 0, n = a[0], sum;
for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) { sum = 0; //sum 为区间 [i, j] 之间的最大和 for (int k = i; k <= j; k++) { sum += a[k]; }
if (sum > max) max = sum; }}
return max;}
看了这个算法，我们不禁会想，有没有能更快的算法呢？毕竟O(n^3)的时间效率是很低的。答案肯定是有的，我们可以令一个数组sum，sum[i]代表了序列从1到i的和。如果要算i到j的和，只需将sum[j]减去sum[i-1]即可，这无疑可以去掉最里层的循环，从而直接调用和的信息，时间效率提高到O(n^2)。
int LSS_Enumerate(int a[]) //最大子段和，枚举算法，O(n^2){int sum[101], i, n = a[0], max = -200000000, t; //sum[i] 表示 a[i] 的前 i 项和
sum[0] = 0;
for (i = 1; i <= n; i++){ sum[i] = sum[i - 1] + a[i];}
for (i = 0; i <= n - 1; i++) //枚举每个可能的子段{ for (int j = i + 1; j <= n; j++) { t = sum[j] - sum[i]; if (t > max) max = t; }}
return max;}
上面两种算法都是朴素算法，枚举每个可能，从而找到最优的解。然而还有没有更优的解呢？答案依旧是肯定的。
我们不妨从小规模数据分析，当序列只有一个元素的时候，最大的和只有一个个可能，就是选取本身；当序列有两个元素的时候，只有三种可能，选取左边元素、选取右边元素、两个都选，这三个可能中选取一个最大的就是当前情况的最优解；对于多个元素的时候，最大的和也有三个情况，从左区间中产生、从右区间产生、左右区间各选取一段。因此不难看出，这个算法是基于分治思想的，每次二分序列，直到序列只有一个元素或者两个元素。当只有一个元素的时候就返回自身的值，有两个的时候返回3个中最大的，有多个元素的时候返回左、右、中间的最大值。因为是基于二分的思想，所以时间效率能达到O(nlgn)。
int LSS_Recursion(int a[], int l, int r) //最大子段和，分治算法，O(nlgn){int m = (l + r) / 2, t = 0, L = 0, R = 0; //L为左区间能取到的最大，R为右区间能取到的最大
if (l == r) //边际条件：当区间元素只有一个的时候返回自身 return a[m];
if (r - l == 1) //边际条件：当区间元素只有两个的时候返回左、右、左右相加三者中的最大值 return Max(Max(a[l], a[r]), a[l] + a[r]);
int LMax = LSS_Recursion(a, l, m); //递归左区间int RMax = LSS_Recursion(a, m + 1, r); //递归右区间
for (int i = m; i >= 1; i--) //左边找一个最大的和{ t += a[i]; if (t > L) L = t;}
t = 0;
for (int i = m + 1; i <= r; i++) //右边找一个最大的和{ t += a[i]; if (t > R) R = t;}return Max(Max(LMax, RMax), L + R); //返回左区间的和、右区间的和、两者连起来的和中最大的}
有了O(nlgn)的递归算法，那还能找到O(n)线性时间的算法么？——动态规划。我们令一个数组f，f[i]表示前i个元素能组成的最大和。如果f[i-1]大于零，则不管a[i]的情况，f[i-1]都可以向正方向影响a[i]，因此可以将a[i]加在f[i-1]上。如果f[i-1]小于零，则不管a[i]再大，都会产生负影响，因此我们还不如直接令f[i]=a[i]。因此状态转移方程就在这里。我们只需在f中扫描一次，找到最大的值就是最大子段的和。
int LSS_DP(int a[]) //求最大子段和，动态规划，O(n){int f[101], n = a[0], max = -200000000; //f[i]表示第 i 个数能构成的最大和， max 表示当前所有中的最大和
f[1] = a[1];
for (int i = 2; i <= n; i++){ if (f[i - 1] > 0) //如果第 i 个数后面一个数能构成的最大子段和大于 0 { f[i] = f[i - 1] + a[i]; //大于就将第 i 个数加入其中 } else f[i] = a[i]; //否则第 i 个数自己组成一个最大子序列
if (f[i] > max) //更新最大值 max = f[i];}
return max;}
以上四个算法，从3个不同的思想解决了最大子段和问题，不管从时间效率还是代码量来说，动态规划都是最优的，仅需要一个辅助数组f来临时存取，因此时间复杂度空间复杂度都是线性的。
下面看一下上一题的推广类型：
求矩阵的最大子矩阵
典型例题：
Pku 1050 To The Max http://acm.pku.edu.cn/JudgeOnline/problem?id=1050
Hdu 1081 To The Max http://acm.hdu.edu.cn/showproblem.php?pid=1081
题目的意思很简单，在一个矩阵里面找它的子矩阵，使得子矩阵数值之和到达最大。其实就是最大子段和问题在二维空间上的推广。考察下面题目中的例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 7
-1 8 0 -2
我们分别用i j表示起始行和终止行，遍历所有的可能：
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {}
我们考察其中一种情况 i=2 j=4，这样就相当与选中了2 3 4三行，求那几列的组合能获得最大值，由于总是 2 3 4行，所以我们可以将这3行”捆绑”起来，变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)的最大子段和，ok，问题成功转化为一维的情况！
核心代码：
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if (i == j) //只有一行的情况，我们只单纯地抽取这行
{
for (k=0;k<n;k++)
{
b[k] = a[i][k];
}
}
else //如果有多行，那么捆绑每一列的和，使之成为一行
{
for (k=0;k<n;k++)
{
b[k] = 0;
for (l=i;l<=j;l++)
{
b[k] += a[l][k];
}
}
}
//这里直接用求求序列的连续最大段就OK了。
}
}
本题的详细完整代码请浏览：
http://blog.csdn.net/jqandjq/archive/2009/02/26/3940653.aspx
求序列的最大上升序列：
经典例题：HDU 1087 Super Jumping! Jumping! Jumping!
http://acm.hdu.edu.cn/showproblem.php?pid=1087
这道理的题意是给一个序列要你求它的最大上升序列（可跳）不用连续
如序列：1 4 7 3 5 6 那么开另一个数组来保存同下标的“最大值”，每一个都要向前找合法的最大b值，如这里的5可以找的合法值为3 4 1，找到最大后便加上同下标的a值，如：
数组a：1 4 7 3 5 6
数组b：1 5 12 4 10 16 à这样找到B中的最大值就OK了！
核心代码：
for (i=0;i<n;i++)
{
b[i] = a[i];
int maxb = 0;
for (j=0;j<i;j++) //找比自己小的里面b最大的
{
if (a[i] > a[j])
{
if (b[j] > maxb)
{
maxb = b[j];
}
}
}
b[i] += maxb;
if (b[i] > maxnum)
{
maxnum = b[i];
}
}
本题的详细完整代码请浏览：
http://blog.csdn.net/jqandjq/archive/2009/02/26/3940712.aspx
本文来自博客，转载请标明出处：http://blog.csdn.net/jqandjq/archive/2009/12/23/5060283.aspx
