JZ67 剪绳子

原题链接
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&&tqId=33257&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述：
输入一个数n，意义见题面。（2 <= n <= 60）
返回值描述：
输出答案。

解体思路

通过数据范围与题目描述可以看出这是一个线性dp题。状态间转移的关键就在于任何长的绳子的切割最优解都是从比其短的绳子的最优解中转移过来的，数据范围比较小，所以可以直接暴力枚举出每一种转移方式，具体分析过程如下:

状态定义

定义 dp[i]：长度为i的绳子其所有分割方法中乘机最大的结果

状态转移

任意一个割点都会产生出两条绳子，故只需要在长的绳子中选择一个合适的割点j，即可将一根长绳子转换成两个短绳子，原问题便转换成了问题规模更小的自问题，转移方程如下
dp[i] = max(dp[i], dp[i - j] * dp[j])

边界设置

对于初始的条件的设置我们可以从状态的定义出发,通过枚举可以发现:

• 长度为0的绳子的最优解： dp[0] = 0
• 长度为1的绳子的最优解： dp[1] = 1
• 长度为2的绳子的最优解： dp[2] = 2
• 长度为3的绳子的最优解： dp[3] = 3
• 长度为4的绳子的最优解： dp[4] = 4
• 长度为5的绳子的最优解： dp[5] = 6 (dp[5] = dp[2] * dp[3])*
  即从长度为5开始的绳子才能通过分割的方式得到最优解,而0到4的绳子都要初始化处理

其他细节

递推的时候需要考虑是否在计算过程中当前定义的数据类型结果是否会溢出，通过分析可知
本题的计算结果不会超过int表示范围，故用int储存结果即可

最终代码(含注释)

class Solution {
public:
    int dp[65];   //定义状态
    int cutRope(int number) {
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; // 边界设置

    //状态转移    
    for(int i = 2; i <= number; i ++ ) 
        for(int j = 0; j <= i; j ++ ) dp[i] = max(dp[i], dp[j] * dp[i - j]);
        return dp[number];    //返回结果
    }
};