当前位置 : 主页 > 编程语言 > java >

《剑指offer》第14题 剪绳子

来源:互联网 收集:自由互联 发布时间:2023-10-10
一、题目 给你一根长度为 n 的绳子,请把绳子剪成整数长的 m 段( m 、 n 都是整数, n 1 并且 m 1 , m = n ),每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多

一、题目

给你一根长度为 n 的绳子,请把绳子剪成整数长的 m 段( m 、 n 都是整数, n > 1 并且 m > 1 , m <= n ),每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少?例如,当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到的最大乘积是 18 。

二、题解

2.1知识点:动态规划

动态规划得基本思想:将待求解的问题分解成若干个相互联系的子问题,先求子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

2.2 解题思路

一旦分出一段长度为1的小段,只会减少总长度,乘积也不会增加,因此长度为2的绳子不分比分开乘积大

长度为3的绳子不分比分开大,长度为4的绳子分成2*2比较大。

同样递推,长度为n的绳子,可以尝试其中一段不可分的为j,如果另一段n-j最大乘积已知,可以遍历所有j找到这个最大乘积。

因此用dp[i]表示长度为i的绳子可以被剪出来的最大乘积,那么后续遍历每个j的时候,外卖取最大的dp[i]表示长度为i的绳子可以被剪出来的最大乘积,那么后续遍历每个j的时候,我们取最大的dp[i]=max(dp[i],j*dp[i-j])就好了。

//可以被分成两份
for(int j = 1; j < i; j++)
    //取最大值
    dp[i] = max(dp[i], j * dp[i - j]);

2.3具体步骤

  • step 1:检查当number不超过3的时候直接计算。
  • step 2:用dp数组表示长度为i的绳子可以被剪出来的最大乘积,初始化前面4个容易推断的。
  • step 3:遍历每个长度,对于每个长度的最大乘积,可以遍历从1到i的每个固定一段,按照上述公式求的最大值。
  • step 4:最后数组最后一位就是答案。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int cutRope (int n) {
        // write code here
        if(n < 2)
            return 0;
        if(n < 4)
            return n -1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        for(int i = 5; i <= n;i++){
            for(int j = 1;j <= i/2;j++){
                dp[i] = Math.max(dp[i],dp[j] * dp[i-j]);
            }
        }
        return dp[n];
    }
}

2.4贪心算法

具体做法:

  • step 1:按照上述思路,不超过3的直接计算
  • step 2:超过3的不断累乘3,然后number不断减去3,直到最后不超过4。
  • step 3:最后乘上剩余的数字。

Java实现代码:

public class Solution {
    public int cutRope(int target) {
        //不超过3直接计算
        if(target <= 3) 
            return target - 1;
        int res = 1;
        while(target > 4){
            //连续乘3
            res *= 3; 
            target -= 3; 
        }
        return res * target;   
    }
}
上一篇:计算机基础知识
下一篇:没有了
网友评论