【剑指Offer】14. 剪绳子

梦里梦外; 2022-11-25 05:24 186阅读 0赞

[NowCode][]

## 题目描述 ##

把一根绳子剪成多段，并且使得每段的长度乘积最大。

n = 2
    return 1 (2 = 1 + 1)
    
    n = 10
    return 36 (10 = 3 + 3 + 4)

## 解题思路 ##

### 贪心 ###

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。

证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。

public class Solution { 
        /** * 解题思路，找出最优解的规律 * 当target等于1，2，3的时候，结果是固定的 * 当target大于3的时候，可以看以下数据 * target=4, 最优解：2 2 * target=5, 最优解：3 2 * target=6, 最优解：3 3 * target=7, 最优解：3 2 2 * target=8, 最优解：3 3 2 * target=9, 最优解：3 3 3 * target=10,最优解：3 3 2 2 * target=11,最优解：3 3 3 2 * target=12,最优解：3 3 3 3 * target=13,最优解：3 3 3 2 2 * target=14,最优解：3 3 3 3 2 * target=15,最优解：3 3 3 3 3 * * 所以不难发现3和2的个数规律 */
        public int cutRope(int target) { 
            if(target < 2)
                return 0;
            if(target == 2)
                return 1;
            if(target == 3)
                return 2;
            
            int of3 = target / 3;
            if(target - of3 * 3 == 1)
                of3--;
            int of2 = (target - of3 * 3) / 2;
            
            return (int)(Math.pow(3, of3)) * (int)(Math.pow(2, of2));
        }
    }

### 动态规划 ###

public class Solution { 
        public int cutRope(int target) { 
            int[] dp = new int[target + 1];
            if(target < 2)
                return 0;
            if(target == 2)
                return 1;
            if(target == 3)
                return 2;
            dp[2] = 2;
            dp[3] = 3;
            for(int i = 4; i <= target; i++) { 
                for(int j = 1; j <= i/2; j++) { 
                    dp[i] = Math.max(dp[i], dp[j]*dp[i-j]);
                }
             }
            return dp[target];
        }
    }
    
    public class Solution { 
        public int cutRope(int n) { 
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for (int i = 2; i <= n; i++)
                for (int j = 1; j < i; j++)
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
            return dp[n];
        }
    }

[NowCode]: https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=33257&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey