本文共 869 字，大约阅读时间需要 2 分钟。

向这种求最值一般用到动态规划

用一个数组dp[n]表示长度为n的绳子分成m段乘积的最大值

分析：和那个青蛙跳台阶有点像，青蛙一次可以跳一阶、二阶，所以青蛙第一次跳一阶后，剩下有n-1个台阶有dp[n-1]种跳法，第一次跳2阶，剩下的n-2阶有dp[n-2]种跳法，结合这两者可得，青蛙跳n个台阶有dp[n] = dp[n - 1] + dp[n - 2]。

对于剪绳子来说，我可以把它只剪一刀的长度k，那么剩下的长度就为n-k, 如果剩下的n-k不剪就是k*(n-k),如果剩下的绳子剪就是k*dp[n-k],所以写几个式子 dp[2] =1 * 1 或者 1 * dp[1] 中的最大 dp[3] = 1 * 2或者1 * dp[2] 、、、2 * 1或者2 * dp[1] 中的最大 dp[4] = 1 * 3或者1 * dp[3] 、、、2 * 2或者2 * dp[2] 、、、3 * 1或者3 * dp[1] 中的最大 。。。。。

import java.lang.Math;public class Solution {
       public int cutRope(int target) {
           int[] dp = new int[target + 1];        dp[0] = 0;        dp[1] = 0;        dp[2] = 1;                for(int n = 2; n <= target; n++) {
                           //j表示剪的长度            for(int j = 1; j < n; j++) {
                   dp[n] = Math.max(dp[n], Math.max(j*dp[n - j], j*(n - j)));            }        }                return dp[target];    }}

转载地址：http://hqhzi.baihongyu.com/