python动态规划算法最大k乘积_动态规划最大K乘积问题
最大K乘积动态规划解决
设I是一个n位十进制整数。如果将I分割为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。
测试：
输入： 2 1 (2是位数，1是分几段)
15 (15是I)
输出：15
输入： 5 2
12345
输出：6170
分析：
1、数组m[i][j]为 将前i位数分成j段的最大乘积
2、数组打底：前1位数，分成1段；前2位数，分成1段；前3位数，分成1段……前n位数，分成1段。(就是先计算出前i位的大小)
3、m[i][j]=Max{m[k][j-1]*a[i-k]}，其意思就是把前k(1<=k
#include
int cal(char* num,int i,int j){
int value=0;
while(j>=i){
value=value*10+(num[i]-'0');
i++;
}
return value;
}
int main(){
int n,k; //n代表整数有n位，k指分成多少段
scanf("%d%d",&n,&k);
getchar();
char num[n+1]; //接收单个字符
int m[n+1][n+1]; //m[i][j] 前i个数字，分成j段
int max,value;
for(int i=1;i
scanf("%c",&num[i]);
}
//数组打底
m[1][1]=num[1]-'0';
for(int i=2;i
m[i][1]=m[i-1][1]*10+(num[i]-'0'); //前i个数字，分成一段
for(int i=2;i<=k;i++){ //分成多少段
max=-1;
for(int j=i;j
for(int d=1;d<=j-1;d++){
value=m[d][i-1]*cal(num,d+1,j);
if(value>max)
max=value;
}
m[j][i]=max;
}
}
printf("最大ｋ乘积为：%d\n",m[n][k]);
return 0;
}
运行截图
运行截图