acwing 25. 剪绳子

习题地址 https://www.acwing.com/problem/content/description/24/

题目描述

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

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

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

样例

输入：

输出：

一道数论题目就是整数可以拆分成几个整数得到乘积最大

但是也可以使用动态规划做

dp[i]表示长度为i的绳子可以拆分得到的最大结果

由于绳子必须拆分 i至少等于2

而长度i的各种拆分方案中假设从长度为j的位置剪下第一刀 (j < i)

那么乘积就是 j*(i-j)

i-j这个长度是否还需要拆分那么取决于dp[i-j]大还是i-j大

最后得到从长度为j的位置剪下第一刀所能得到的最大乘积结果

j的取值范围是 1到i-1的. 最后代码如下:

class Solution {

public:

    int maxProductAfterCutting(int length) {

        vector<int> dp(length+,);

        for(int i = ;i <= length;i++){

            for(int j= ;j <i;j++){

                dp[i] = max(dp[i] ,max(j*(i-j) ,dp[i-j]*j ));

            }

        }

        return dp[length];

    }

};

巴特西

acwing 25. 剪绳子

样例

最新文章

热门文章