题目来源：https://www.acwing.com/problem/content/24/
转载自：https://www.acwing.com/solution/content/2537/

题目描述

具体代码

设置一个数组dp[n+1]
，dp[ i ]
存储绳子长度为i 时的最大乘积。依题意，绳子至少被剪一次，所以绳子长度最小为2。外层for循环从绳长为i=2的情况开始依次计算，直到计算到绳长为n的情况。

内层for循环：当绳长为i时，由于已知至少剪一刀，我们索性假设第一刀剪在长度为j的位置(即第一段绳子长度为j
)。剩下的那段长度为( i - j )
的绳子就变成了“可剪可不剪”。那究竟是“不剪了”得到的乘积大呢，还是“继续剪余下的这段”得到乘积更大？我们不知道，所以需要两种情况都计算一下进行比较。其中，“不剪了”得到的乘积是j * ( i - j )
，“继续剪”得到的乘积是j * dp[ i - j ]
。取其中的较大值，就是“第一剪在j位置”能得到的最大乘积。而第一剪的所有可能位置是1,2,…,i-1。依次计算所有可能情况，取最大值即为dp[ i ]的值。

由上述过程可知，只有先依次计算出**dp[2],dp[3],…**的值，才能得到dp[n]
的值。此为动态规划。

class Solution {
    public int maxProductAfterCutting(int length) {
        int[] dp = new int[length+1];
        for(int i = 2; i <= length; i++) {
            for(int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j])); 
            }
        }
        return dp[length];
    }
}

运行结果

输入：

8

输出：

18

上述代码和解释均转载自 AcWing SH2OCN 的评论（点击链接即可跳转至原文处）~！