最大k乘积问题动态规划

设I是一个 n位十进制整数。如果将I划分为 k段，则可得到k个整数。这k个整数的 乘积称为I的一个 k乘积。试设计一个算法，对于给定的 I和 k，求出 I的最大 k乘积。 对于给定的I和k，计算 I的最大 k乘积.

输入： 第1 行中有2个正整数n和 k。正整数 n是序列 的长度；正整数k是分割的段数。接下来的一行中是一个n位十进制整数。（n<=10） 输出： 输出最大k乘积 分析： c++代码：

//最大k乘积问题 
#include<bits/stdc++.h>
using namespace std;
#define N 100
int dp[N][N],number[N];//dp前i位数划分j段的最大值，
int n ,k,num;//n位，划分k段 ,数值 

void getNumber()//将数值存到数组中 
{
          
     
 int b = 0;
 for(int i=n;i>0;i--){
          
   
  b = num%10;
  num = num/10;
  number[i] = b;
 }
 for(int i=1;i<=n;i++)
  cout<<number[i]<<" ";
 cout<<endl; 
}

int countNum(int p, int q)//获取第p~q位的数值 ,数组下标从0开始 
{
          
   
 int mm = 0;
 for(int i=p;i<=q;i++){
          
   
  mm = mm*10+number[i];
 }
 return mm; 
 } 
 main()
{
          
   
 ifstream f1("1.txt");
 ofstream f2("2.txt");
 f1>>n;
 f1>>k;
 f1>>num;
 cout<<n<<","<<k<<","<<num<<"
";
 if(k==1){
          
   
  cout<<"最大k乘积为："<<num<<endl;
  f2<<"最大k乘积为："<<num<<endl;
  return 0;
 } 
 getNumber();
 for(int i=1;i<=n;i++){
          
   //初始化 
  dp[i][1] = countNum(1,i);
 }
 for(int i=1;i<=n;i++){
          
   //位数 
  for(int j=1;j<=k;j++){
          
   //分段数 
   if(j>i){
          
    //分段数大于位数 ，结束本次循环 
    dp[i][j] = 0; break;
   }else if(j==1){
          
    //上面做过了,结束当前循环 
    continue;
   }else{
          
   
    int max =0, temp =0;
    for(int a=i-1;a>=1;a--){
          
   
     int ff = countNum(a+1,i);
     temp = ff * dp[a][j-1];
     if(temp>max) max =temp;
    }
    dp[i][j] = max;
   }
  }
 }
 cout<<"最大k乘积为："<<dp[n][k]<<endl;
 f2<<"最大k乘积为："<<dp[n][k]<<endl;
 f1.close();
 f2.close();
 return 0;
}

运行结果：