本文主要是介绍(三) POJ1050，动态规划必做题目，经典程度五颗星。这个题目的前身就是：求最大子序列和。 先来看最大子序列和。有一串数，有正有负，如2，-1，5，4，-9，7，0，3，-5。求：这，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
(三) POJ1050，动态规划必做题目，经典程度五颗星。这个题目的前身就是：求最大子序列和。
先来看最大子序列和。有一串数，有正有负，如2，-1，5，4，-9，7，0，3，-5。求：这一串数中，和最大的一段。比如说，从第一个数2开始，发现下一个为-1，加下-1后和显然会变小。再往后看，第三个数是5，所以上一个-1还是要选的，这样才能加上5。哎，不看了，这样求最大和还不得累死。嘿嘿，这时DP就派上用场了。
设这串数为X1 X2 X3 … Xn, 用dp(i,j)表示从Xi…Xj的最大子序列和。
按照DP的思路，想办法减小问题的规模。有n个数，怎样能减少到n-1数？想办法把最后一个数Xn去掉，问题规模就能减少到n-1。
通过观察可以发现：X1…Xn的最大子序列可以分为两类：以Xn结尾、不以Xn结尾。不以Xn结尾的最大子序列，其实就是X1…Xn-1的最大子序列，发现这点很重要。
这样就有：dp( i, j ) = Max( dp( i, j-1 ), Last( j ) ).其中Last( j )表示以Xj结尾的最大子序列的和。
功夫不负有心人，终于把问题规模减少了。但是，一波未平一波又起，新的问题又出现了。Last( j )如何求？即，求以Xj结尾的最大子序列的和。再用DP求解。
Last( j )和Last( j-1 )之间的关系比较简单。Last(j )的值里面必然会包括Xj的值，到底有没有Last( j-1 )也很简单，主要取决于Last( j-1 )是正还是负。
这样就有：Last( j ) = Max( Xj, Last( j-1) + Xj );
状态转换方程：
dp( i, j ) = Max( dp( i, j-1 ), Last( j ) )其中：dp(i,j)表示从Xi…Xj的最大子序列和
Last( j ) = Max( Xj, Last( j-1 ) + Xj ); 其中：Last( j )表示以Xj结尾的最大子序列的和
现在，回到POJ1050。想想能不能利用上面的结果？求最大子矩阵，那么只要确定了子矩阵有几行、几列即可。这样，可以枚举子矩阵的行数和列数。
比如，当子矩阵只要一行时，那么只关心它的列从哪开始到那结束就行。哦，这其实就是一个最大子序列和的问题。这一行就是这一串数，求和最大的一段。那么当子矩阵有两行时，怎么办？如何把两行变为一行？一个聪明的想法就是：把这两行按照对应的列加起来。
好了问题已经漂亮的解决了：在原矩阵中任意画出一部分，然后按照对应的列加起来，问题就转变为一个最大子序列和的问题
//下面的是 一维数组 ，最大长序列 的和 最大子串和:
import java.util.Arrays;/*
其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧：设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。假如对于子段：9 2 -16 2 temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是：如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段)，也就是说 状态转移方程：temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];对于刚才的例子 temp： 9 11 -5 2，然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数：import java.util.Arrays;/*其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧：设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。假如对于子段：9 2 -16 2 temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是：如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段)，也就是说 状态转移方程：temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];对于刚才的例子 temp： 9 11 -5 2，然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数：*/ public class TheMaxSubString {public static void main(String[] args){// int [] buff ={1,-1,3,4,5,6,7,8,-1,128};int[] buff ={ 4, 9, -17, 7 };System.out.println(Arrays.toString(buff));System.out.println(DpLineMaxSum(buff, 4));int[][] buff2 ={{ 0, -2, -7, 0 },{ 9, 2, -6, 2 },{ -4, 1, -4, 7 },{ -1, 8, 0, -2 } };System.out.println(DpMatrixMaxSum(buff2, 4, 4));}// 最大矩阵和：二维数组public static int DpMatrixMaxSum(int buff[][], int row, int col){int maxSum = 0;int virtualLine[] = new int[col];// 从哪一行开始往下求和for (int i = 0; i < row; i++){// 以i行为基准，需要循环多少次，求for (int temp = 0; temp < row - i; temp++){int j = i + temp;// 以i为基准啊进行往下求和for (int column = 0; column < col; column++){int sum = 0;// 按照列进行相加，for (int k = i; k <= j; k++){sum += buff[k][column];}virtualLine[column] = sum;}int value = DpLineMaxSum(virtualLine, col);maxSum = (maxSum < value) ? value : maxSum;}}return maxSum;}// 最大子串和:一维数组public static int DpLineMaxSum(int buff[], int n){int e = 0;int max = 0;int[] temp = Arrays.copyOf(buff, n);for (int i = 1; i < n; i++){temp[i] = (temp[i - 1] > 0 ? temp[i - 1] : 0) + buff[i];if (max < temp[i]){max = temp[i];e = i;}}System.out.println("line-->" + e);return max;} }
这篇关于(三) POJ1050，动态规划必做题目，经典程度五颗星。这个题目的前身就是：求最大子序列和。 先来看最大子序列和。有一串数，有正有负，如2，-1，5，4，-9，7，0，3，-5。求：这的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
