[算法题]最小m划分(划分DP)

题目描述

给定 n 个整数组成的序列，将序列分割为 m 段，如何分割才能使这 m 段子序列的和的最大值达到最小？

题解

状态表示 dp[i][j]表示前i个元素划分j段子序列和的最大值的最小值
状态转移 dp[i][j]=min{dp[i][j], max{dp[k][j-1],dp[i][1]-dp[k][1]}}，其中前k个元素是前j-1段，k+1到末尾是最后一段。
初始化 dp[i][1]=对应子数组原始元素和

todo

for循环的终止条件还有需继续思考为什么不是注释的？或者换成注释要改哪里。

代码

public class Main {

	public static void main(String args[]) {

		int[] arr= {9,8,7,6,5,4,3,2,1};

		int m=3;

		int minMaximum=minMaxMSegSum(arr,m);//9,8/,7,6/,5,4,3,2,1

		System.out.println(minMaximum);

	}

	public static int minMaxMSegSum(int arr[],int m) {

		int[][] dp=new int[arr.length+1][m+1];

		int sum=0;

		for(int i=0;i<arr.length;++i) {

			sum=sum+arr[i];

			dp[i+1][1]=sum;

		}

		for(int i=2;i<arr.length+1;++i) {//

			for(int j=2;j<=m&&j<=i;++j) {//

				dp[i][j]=Integer.MAX_VALUE;//

				for(int k=1;k<i;++k) {//&&j-1<=k?

					dp[i][j]=Math.min(dp[i][j], Math.max(dp[k][j-1],dp[i][1]-dp[k][1]));//

				}

			}

		}

		return dp[arr.length][m];

	}

}

巴特西

[算法题]最小m划分(划分DP)

题目描述

题解

todo

代码

最新文章

热门文章