【数学专题】剑指 Offer 14- I. 剪绳子-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2024年12月16日下午9:49

时间复杂度O(1)
空间复杂度O(1)

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len <= 3)
            return bamboo_len - 1;
        int a = bamboo_len / 3;
        int b = bamboo_len % 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;
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月13日下午10:16

解题思路
– 动态规划的实现有点类似于遍历破解，只是提供了更加规范的一些套路
– 定义int[] dp=new int[n+1] 去存放长度为1,2,3…n的中间数据，为什么要n+1，因为把数组的下标作为长度，最长的长度是n，那么数组的长度应该是n+1（下标0未被使用）
– 两层循环，第一层循环用于定义不同长度，i=2~n；第二层循环用于定义第一段的长度j，j=2~ i-1；
– dp[i]值的条件应该是=Math.max(j * (i – j), j * dp[i – j]); 并且每一次j循环都要尝试去更新这个dp[i]值
– 这个Math.max(j * (i – j), j * dp[i – j])有点类似于递归，它是如何在程序中实现的呢?还是因为我们给了起点值dp[2] = 1，dp[i]的设置都是从小到大完成的，所以外层循环一定要是2~n的遍历
【题解1】动态规划

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        // 把长度为n的问题转换成n-1的
        // 先分割成2段，左边为j，右边为bamboo_len-j
        // 右边不继续分割，那么乘积为 j*(bamboo_len-j)
        // 右边要继续分割，那么乘积为j*(dp[bamboo_len-j]),结果取最大值Max(j*(bamboo_len-j),j*(dp[bamboo_len-j]))
        // 左边的j变动范围是[2,bamboo_len-1]
        // 其中对于长度n来说，分成2段，1*(n-1)是无任何收益的，所以至少分给2
        int[] dp = new int[bamboo_len + 1];
        // 这个是起点，必须要有
        dp[2] = 1;
        // 不同长度的绳子的循环（题目规定的）
        for (int i = 2; i <= bamboo_len; i++) {
            // 不同的第一段j长度的循环（j从2开始，因为j=1没有任何dp可能变大的收益）
            for (int j = 2; j <= i - 1; j++) {
                // 当前第一段j时，能获取到的最大乘积
                int tmpt = Math.max(j * (i - j), j * dp[i - j]);
                // 更新dp[i]
                dp[i] = Math.max(dp[i], tmpt);
            }
        }
        return dp[bamboo_len];

    }
}

【题解2】贪心，前提是要知道数学规律
– n<=3的时候，最大乘积=n-1
– n>=4的时候，最大乘积就是把n尽可能分成3的若干份，即n=a3+b
– 当b=0，结果为Math.pow(3,a);
– 当b=1，需要n=(a-1)3+(3+1),结果为 Math.pow(3,a-1)(22) ，其中22是分割4获取到的
– 当b=2，结果Math.pow(3,a)2

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        // n=3，结果是2；n=2，结果是1.
        if (bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int a = bamboo_len / 3;
        int b = bamboo_len % 3;
        if (b == 0) {
            // 【错误点】Math.pow的结果是double，需要转换成int
            return (int) Math.pow(3, a);
        } else if (b == 1) {
            return (int) Math.pow(3, a - 1) * 4;
        } else {
            return (int) Math.pow(3, a) * 2;
        }

    }
}

错误点1：Math.pow的结果是double，需要转换成int

0 赞同 0 条回复

Aatorx 永久会员 2024年12月11日下午2:46

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if (bamboo_len <= 2) {
            return 1;
        }
        if (bamboo_len == 3) {
            return 2;
        }
        int k = bamboo_len / 3;
        bamboo_len = bamboo_len % 3;
        if (bamboo_len == 1) {
            return pow(3, k-1) * 4;
        }
        else if (bamboo_len == 0) {
            return pow(3, k);
        }
        else if (bamboo_len == 2) {
            return pow(3, k) * 2;
        }
        return 0;
    }
};

尽量将绳子切分成长度为3。若出现余数为1，则需要将最后一段变为长度为4。
时间复杂度O(1)，空间复杂度O(1)。

0 赞同 0 条回复

Xiang. 永久会员 2024年12月11日上午10:27

class Solution {
    //思路：利用均值不等式求出乘积最大值 L(m)=(n/m)^m 对此式求导（利用对数法），可以证明当 m=n/e 时，
    //乘积取最大，此时每段绳子的长度为 n/(n/e)=e，自然对数e的值为2.718，显然接近3，
    //所以切分为3的优先级最高
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=3) return 2;
        int a=bamboo_len/3;
        int b=bamboo_len%3;
        if(b==0) return (int)Math.pow(3,a);
        else if(b==1) return (int)Math.pow(3,a-1)*4;
        else return (int)Math.pow(3,a)*2;
    }
}
时间空间复杂度均为：O（1）

0 赞同 0 条回复

jaron 普通 2024年12月11日上午8:41

数学题~

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len == 2) {
            return 1;
        }
        if (bamboo_len == 3) {
            return 2;
        }
        // 尽量分成每份都是3
        int res = bamboo_len / 3;
        int remain = bamboo_len % 3;
        if (remain == 0) {
            return (int) Math.pow(3, res);
        } else if (remain == 1) {
            // 余1就差一个3组成4
            return (int) Math.pow(3, res - 1) * 4;
        } else {
            return (int) Math.pow(3, res) * 2;
        }
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月10日下午10:30

class Solution {
    /**
     * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
     * 返回 你可以获得的最大乘积 。
     * 
     * 解题思路：三种解法
     * 解法一：递归 + 备忘录 = 记忆化搜索
     * 解法二：动态规划     
     *      1. dp 数字及其下标含义
     *          dp[i]：整数 i 拆分为 k 个后的乘积最大化
     *      2. 递推公式
     *          每一个位置，从 1 开始拆分
     *              dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]);
     *      3. 初始化
     *          dp[2] = 1;
     *      4. 遍历顺序：顺序遍历
     *      5. 打印
     *      
     * 解法三：数学推导，三等分     
     * @param n
     * @return
     */
    public int cuttingBamboo1(int n) {
        int[] memo = new int[n + 1];
        return dfs(n, memo);
    }

    private int dfs(int n, int[] memo) {
        // 越界判断
        if (n == 0 || n == 1) {
            return n;
        }
        // 判断是否已经计算过
        if (memo[n] != 0) {
            return memo[n];
        }

        // 计算 memo[n]，它的乘积的最大值
        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            // 是上一次计算的大，还是当前计算的大
            res = Math.max(res, i * Math.max(dfs(n - i, memo), n - i));
        }
        memo[n] = res;
        return res;
    }


    /**
     * 方法二：动态规划
     * @param n
     * @return
     */
    public int cuttingBamboo2(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }

    /**
     * 方法三：数学公式，3 等分时，乘积最大
     * @param n
     * @return
     */
    public int cuttingBamboo(int n) {
        if (n <= 3) {
            return n - 1;
        }

        int a = n / 3, b = n % 3;
        if (b == 0) {
            return pow(3, a);
        }else if (b == 1) {
            return pow(3, a - 1) * 4;
        }
        return pow(3, a) * 2;
    }

    // 快速幂
    private int pow(int n, int x) {
        int m = n;
        int res = 1;
        while (x != 0) {
            if ((x & 1) == 1) {
                res *= m;
            }
            m *= m;
            x >>= 1;
        }
        return res;
    }
}

思路：记忆化搜索、动态规划、数学推导三等分
时间复杂度：O(n^2^)、O(n^2^)、O(n)。
空间复杂度：O(n)、O(n)、O(1)。

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午9:38

思路：使用动态规划处理纯数学推导解法头疼不想看

class Solution {
    public int cuttingBamboo(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            for(int j = 2; j < i; j++){
                // (j * (i - j) 剩余部分 不砍 
                // j * dp[i - j] 剩余部分 继续砍 
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月10日下午9:27

动态规划

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<2) return 0;
        if(bamboo_len==2) return 1;
        if(bamboo_len==3) return 2;

        int[] dp=new int[bamboo_len+1];

        dp[1]=1;
        dp[2]=2;
        dp[3]=3;

        for(int i=4;i<=bamboo_len;i++){
            int maxProduct=0;
            for(int j=1;j<=i/2;j++){
                maxProduct=Math.max(maxProduct,dp[j]*dp[i-j]);
            }
            dp[i]=maxProduct;
        }

        return dp[bamboo_len];
    }
}

On2 on

0 赞同 0 条回复

晓宇普通 2024年12月10日下午9:14

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 2) return 1; 
        else if(bamboo_len == 3) return 2;
        int res = bamboo_len / 3;
        int mod = bamboo_len % 3;

        // 长度大于或等于5继续切乘积可变大
        if(mod == 0) return pow(3,res);
        else if(mod == 1) return pow(3, res - 1) * 4;
        else return pow(3, res) * 2;
    }
    // o(n) o(1)
};

0 赞同 0 条回复

月下足迹普通 2024年12月10日下午6:25

lass Solution {
public int cuttingBamboo(int bamboo_len) {
// 边界条件
if (bamboo_len <= 3) {
return bamboo_len – 1; // 竹子长度 <=3 时，直接返回最大乘积
}

    // 最大化乘积
    int res = 1;
    while (bamboo_len > 4) { // 优先切长度为 3 的段
        res *= 3;
        bamboo_len -= 3;
    }

    // 剩余部分直接乘
    res *= bamboo_len;
    return res;
}

}

0 赞同 0 条回复

【数学专题】剑指 Offer 14- I. 剪绳子

共以下 10 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 14- I. 剪绳子

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复