欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer 剪绳子 java

程序员文章站 2022-04-15 18:57:11
题目描述给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。与主站 整数拆分 一致动态规划:对于正整数n,当n>=2时,可以拆分成至少两个正整数和。令k是拆分出的第一个正整数,则剩下的部分是n-k,n-k可以不继续拆分,也...

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

动态规划:

  • 对于正整数n,当n>=2时,可以拆分成至少两个正整数和。

  • 令k是拆分出的第一个正整数,则剩下的部分是n-k,n-k可以不继续拆分,也可以继续拆分成至少两个正整数的和。

  • 每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积。(动态规划)

  • 创建数组dp[n+1],其中dp[i]表示将正整数拆分成至少两个正整数的和之后,这些正整数的最大乘积。特别地,0和1不可以拆分,所以dp[0]=dp[1]=0

  • 当正整数i>=2时: 将i拆分成j和i-j的和,如果i-j不再拆分,则乘积为j*(i-j);如果i-j继续拆分,则乘积为j*dp[i-j]

  • 因此,当j固定时,dp[i] = max(j*(i-j),j*dp[i-j])

代码:

class Solution {
    public int cuttingRope(int n) {
        int dp[] = new int[n+1];
        for(int i = 2;i<=n;i++){
            int curmax = 0;
            for(int j = 1;j<i;j++){
                curmax = Math.max(curmax,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i] = curmax;
        }
        return dp[n];
    }
}

本文地址:https://blog.csdn.net/stonney/article/details/109637819