剪绳子

题目描述

给你一根长度为 n n n 绳子，请把绳子剪成 m m m 段（m、n 都是整数， 2 ≤ n ≤ 58 2≤n≤58 2≤n≤58 并且 m ≥ 2 m≥2 m≥2）。

每段的绳子的长度记为 k [ 1 ] 、 k [ 2 ] 、 … … 、 k [ m ] k[1]、k[2]、……、k[m] k[1]、k[2]、……、k[m]

k [ 1 ] k [ 2 ] … k [ m ] k[1]k[2]…k[m] k[1]k[2]…k[m] 可能的最大乘积是多少？

样例

例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。

输入：8

输出：18

题解：

这是一个完全背包问题，把一个自然数N拆分成若干个数相加，且拆分的数的个数至少两个以上，求拆分数字的乘积的最大值。
定义集合： f [ i ] [ j ] f[i][j] f[i][j]的含义从前i个数选，和为j选法的集合
属性：MAX
集合的划分：通过选不选第i个数划分集合
不选： f [ i ] [ i ] = f [ i − 1 ] [ j ] f[i][i] = f[i-1][j] f[i][i]=f[i−1][j]

选1-k个： f [ i ] [ j ] = m a x ( f [ i ] [ j − i ] ∗ i , f [ i ] [ j − 2 i ] ∗ i 2 , . . . , f [ i ] [ j − k i ] ∗ i k , ⋅ ⋅ ⋅ ) f[i][j] = max(f[i][j-i]*i,f[i][j-2i]*i^2,...,f[i][j-ki]*i^k,···) f[i][j]=max(f[i][j−i]∗i,f[i][j−2i]∗i2,...,f[i][j−ki]∗ik,⋅⋅⋅)
等价变形 f [ i ] [ j − i ] = m a x ( f [ i ] [ j − 2 i ] ∗ i , . . . , f [ i ] [ j − k i ] ∗ i k − 1 , ⋅ ⋅ ⋅ ) f[i][j-i] = max(f[i][j-2i]*i,...,f[i][j-ki]*i^{k-1},···) f[i][j−i]=max(f[i][j−2i]∗i,...,f[i][j−ki]∗ik−1,⋅⋅⋅)
选1-k个： f [ i ] [ j ] = f [ i ] [ j − i ] ∗ i f[i][j] = f[i][j-i]*i f[i][j]=f[i][j−i]∗i

综上： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − i ] ∗ i ) f[i][j] = max(f[i-1][j],f[i][j-i]*i) f[i][j]=max(f[i−1][j],f[i][j−i]∗i)

N = 2 和 3的时候特判一下

代码：

O ( n 2 ) O(n^2) O(n2)

class Solution {
public:
    int maxProductAfterCutting(int length) {
        int ans = 0, cnt = 0;
     
        int f[60][60] = {0};
        for (int i = 0; i <= length; i ++)  f[i][0] = 1, f[0][i] = 1;
        
        for (int i = 1; i <= length; i ++){
            for (int j = 1; j <= length; j ++){
                f[i][j] = max(f[i][j],f[i-1][j]);
                if (j >= i) f[i][j] = max(f[i][j], f[i][j-i]*i);
            }
        }
        
        if (length == 2 || length == 3)    return length - 1;
        return f[length][length]; 
    }
        
};