減繩子問題動态規劃求解

問題描述

給你一根長度為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;
}