JZ67 剪绳子

2021年9月14日22:31:52
动态规划
res代表 i时 的 最大值
i为1,2,3 时 不分割 最大值 为1,2,3
为什么是 j<= i/2 因为 大于时 重复算了一遍 2,8 -> 8,2

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


}

贪心

public class Solution {
    public int cutRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    } 
}