减绳子问题动态规划求解

问题描述

给你一根长度为N的绳子，请把绳子剪成M段（m,n都是整数），每段绳子的长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2] …的乘积最大

约定：剪出来的每段小绳子也必须为整数

例如 绳子长度8 剪成3段 最大乘积18 = 2*3 *3

输入

输入只有1行，分别为N，M；

其中N表示绳子的长度，M表示要剪成的段数。

0<=N<=1000

0<=M<=100

输出

输出只有一行，maxsum

表示所有小段绳子的最大乘积

输入样例

8 3

输出样例

18

思路

典型的动态规划问题。

创建一个二维数组m[i][j]表示长度为i的绳子裁剪成j段的乘积最大值。

当i>j时，存在k(1<=k<=i-j+1)使得m[i][j]=k*m[i-k][j-1]

这里给出状态转移方程。

代码

#include <iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
long long m[1001][101];
//m[i][j]表示把长度为i的绳子裁剪为j段的最大乘积
//for(i=1;i<=n;i++)  m[i][1]=i;裁成1段乘积就是原长度
//for(j=1;j<=m;j++) if(i<j) m[i][j]=0;//没法裁剪
//if(i==j)长度为i的裁成i份，每一份都是1，那么m[i][j]=1
//if(i>j)  这才是我们要讨论的问题
//m[i][j]=max{m[i-k][j-1]*k}(1<=k<=i-j+1);
int main()
{
    int N,M;//N表示绳子的长度，M表示要剪成的段数
    cin>>N>>M;
    if(M>N){
        cout<<0;//每段绳子必须是整数，如果M>N,这个乘积为0
        return 0;
    }else if(N==M){
        cout<<1;//M=N,只有1种裁剪方法，每段绳子都是1，乘积也为1
        return 0;
    }else{
        //初始条件，用于迭代
        //长度为i的绳子裁成1段时，最大乘积为i
        for(int i=1;i<=N;i++)
            m[i][1]=i;
        //动态规划 i从1开始，j从2开始
        for(int i=1;i<=N;i++)
        for(int j=2;j<=M;j++){
            if(i==j)//只有1种裁剪方法，每段都是1
                m[i][j]=1;
            else if(i<j)//没有裁剪方法
                m[i][j]=0;
            else{//规划最优值
                int k=1;
                m[i][j]=m[i-1][j-1]*1;//m[i][j]赋初值
                //for循环更新m[i][j]
                for(k=1;k<=i-j+1;k++)//为保证每段小绳子长度>=1,1<=k<=i-j+1
                    if(m[i][j]<m[i-k][j-1]*k)
                        m[i][j]=m[i-k][j-1]*k;
            }
        }
    }
    cout<<m[N][M];
    return 0;
}