最小m段和 经典dp问题

标签: 算法

在这里插入图片描述当j=1时,dp[i][1]表示的是长为i的整个序列的和;
当j>1时:
for(k=1; k<=i; k++)
x=min(dp[k][j-1], dp[i][1] - dp[k][1])
dp[i][j]=max(x)

在这里插入图片描述代码:

#include <stdio.h>
 
int dp[100][100] ;					//dp[i][j]存储0~i的j个分组的和的最大值的最小值 
 
int MAX(int n1, int n2){
	
	if(n1 < n2)	
		return n2 ;
	else 
		return n1 ;
} 
 
void calculate(int a[], int n, int m){
	
	int i, j, k, temp, min ;
 
	if(n == 0){
		printf("数组为空!\n") ;
		return ;
	}
 
	for(i=1; i<=n; i++){			//当j=1时表示整个序列的和
		dp[i][1] = dp[i-1][1] + a[i] ;
	}
 
	for(i=1; i<=n; i++){
		
		for(j=2; j<=m; j++){
			
			min = 99999 ;			
 
			for(k=1; k<=i; k++){	//最后一段的每一次的分组情况
 
				temp = MAX(dp[k][j-1], dp[i][1] - dp[k][1]) ;
				
				if(temp < min){		//寻找最小值并赋值
					min = temp ;
				}
			}
			dp[i][j] = min ;
		}
	}
	printf("%d", dp[n][m]) ;
}
 
int main() 
{
	int a[100] ;
	int i, n, m ;
 
	printf("请输入数组长度:") ;
	scanf("%d", &n) ;	
	printf("请输入分段个数:") ;
	scanf("%d", &m) ;
	printf("请输入数组内容:") ;
 
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]) ;
	} 
	
	calculate(a, n, m) ;
 
	printf("\n") ;
 
	return 0 ;
}
版权声明:本文为qq_32256033原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_32256033/article/details/106439588