剑指offer面试题14(java版):剪绳子

import java.math.BigInteger;

class Solution {
    public int cuttingRope(int n) {
        if(n<2)
            return 0;
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        /*
        d[i]表示长度为i的绳子剪完后各段乘积的最大值, 最终目标是dp[n]
        dp[i]可以看成是长度为i-k的绳子的最大值和长度为k的绳子的最大值的乘积, 子问题最优, 所以dp[i]也是最优
        状态转移方程: dp[i] = max(dp[i], dp[i-k]*dp[k])
        */
        //下面的初始值不同于上面的特殊情况, 上面是必须剪一刀, 下面的三个初始值不用再减了
        BigInteger[] dp = new BigInteger[n+1];
        dp[1] = new BigInteger("1");//内循环中会用到这个值
        dp[2] = new BigInteger("2");
        dp[3] = new BigInteger("3");
        for(int i=4; i<=n; i++){
            //初始化dp[i]
            dp[i] = new BigInteger("0");
            //长度为i的绳子有i-1个剪切位置; 不论i是奇数还是偶数, 只考虑前i/2个剪切位置即可, 后面的剪切位置是重复的
            for(int j=1; j<=i/2; j++){
                //因为j和i-j都小于i, 所以这是自底向上的计算方式
                dp[i] = dp[i].max(dp[j].multiply(dp[i-j]));
            }
        }
        return dp[n].mod(new BigInteger("1000000007")).intValue();
    }
}

class Solution {
    public int cuttingRope(int n) {
        if(n<2)
            return 0;
        if(n==2)
            return 1;
        if(n==3)
            return 2;
        /*
        d[i]表示长度为i的绳子剪完后各段乘积的最大值, 最终目标是dp[n]
        dp[i]可以看成是长度为i-k的绳子的最大值和长度为k的绳子的最大值的乘积, 子问题最优, 所以dp[i]也是最优
        状态转移方程: dp[i] = max(dp[i], dp[i-k]*dp[k])
        */
        //下面的初始值不同于上面的特殊情况, 上面是必须剪一刀, 下面的三个初始值不用再减了
        int[] dp = new int[n+1];
        dp[1] = 1;//内循环中会用到这个值
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4; i<=n; i++){
            //长度为i的绳子有i-1个剪切位置; 不论i是奇数还是偶数, 只考虑前i/2个剪切位置即可, 后面的剪切位置是重复的
            for(int j=1; j<=i/2; j++){
                //因为j和i-j都小于i, 所以这是自底向上的计算方式
                dp[i] = Math.max(dp[i], dp[j]*dp[i-j]);
            }
        }
        return dp[n];
    }
}

public class Solution {
    public int cutRope(int target) {
        if(target<2)
            return 0;
        if(target==2)
            return 1;
        if(target==3)
            return 2;
        //arr[i]表示长为i的绳子剪成m段后,各段乘积的最大值
        int[] dp = new int[target+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4; i<=target; i++){
            //长为i的绳子在题目约束下有i-1个剪切位置, 但只剪到i/2处就行了, 后面的情况重复了
            for(int j=1; j<=i/2; j++){
                if(dp[j]*dp[i-j] > dp[i])
                    dp[i] = dp[j]*dp[i-j];
            }
        }
        return dp[target];
    }
}

public class Solution {
    public int cutRope(int target) {
        if(target < 2) // 长度小于2没法切. 长度为1的绳子没法切;但是某个绳子切完后可以包含长为1的绳子,注意这二者的区分
            return 0;
        if(target==2)
            return 1;
        if(target==3)
            return 2;
        // products的索引为1,2,3时只是表示绳子长度为1,2,3
        // products的索引i大于3时,表示长为i的绳子剪切后各段乘积能得到的最大值
        int[] products = new int[target+1]; // 长度加一后,最后一个索引是length, 方便表示
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;
        for(int i=4; i<=target; i++){
            // for(int j=1; j<=i-1; j++){ //长为i的绳子,切割位置可以是{1,2,3,...i-1}
            for(int j=1; j<=i/2; j++){ // 长为3的绳子,可以切成1,2; 2,1; 效果是一样的,所以只用切i/2次就行    // 可能要问不是还能切成1,1,1这种吗? 为什么只切1次? 1,1,1这种情况在1,2中已经考虑过了,1,1是2的两个子问题. 这里要明确子问题与更小的子问题的关系
                if(products[i] < products[j]*products[i-j])
                    products[i] = products[j]*products[i-j];
            }
        }
        return products[target];
    }
}