《剑指offer》Java版--14.剪绳子

2023-12-28 10:39:47

剑指offer原题14:剪绳子
给你一根长度为n的绳子,请把绳子剪成m段(mn都是整数n>1并且m>1),每段绳子的长度记为O],[1],·-,[m]。请问O]xk[1]x···Xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是 18。
LeetCode原题:https://leetcode.cn/problems/jian-sheng-zi-lcof/description/

思路一:数学

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 3) return bamboo_len - 1;
        int count = bamboo_len / 3;
        int mod = bamboo_len % 3;
        int res;
        if(mod == 0) res = (int)Math.pow(3, count);
        else if(mod == 1) res = (int)Math.pow(3, count - 1) * 4;
        else res = (int)Math.pow(3, count) * 2;
        return res;
    }
}

思路二:动态规划

对于长度为n的绳子,定义F(n)为最大乘积。如果剪成2段,则F(n) = max(F(n-i) * F(i)) 其中 0<i<n。然后要求F(i)和F(n-i),这个时候就相当于从上往下的递归。可以改造成从下往上的递推。

class Solution {
   public int cuttingBamboo(int bamboo_len) {
       if (bamboo_len <= 3) {
           return bamboo_len - 1;
       }
       int[] f = new int[bamboo_len + 1];
       f[2] = 1;
       for (int i = 3; i <= bamboo_len; i++) {
           f[i] = Math.max(Math.max(2 * (i - 2), 2 * f[i - 2]), Math.max(3 * (i - 3), 3 * f[i - 3]));
       }
       return f[bamboo_len];
   }
}

文章来源:https://blog.csdn.net/m0_56199449/article/details/135258083
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。