题目描述:
给你一根长度为 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。
提示:
2 <= n <= 58
class Solution { public int cuttingRope(int n) { /* dp五部曲: 1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i] 2.状态转移:dp[i]有两种途径可以转移得到 2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个 2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2 两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值 3.初始化:初始化dp[1]=1即可 4.遍历顺序:显然为正序遍历 5.返回坐标:返回dp[n] */ // 定义dp数组 int[] dp = new int[n + 1]; // 初始化 dp[1] = 1; // 指长度为1的单独乘积为1 // 遍历[2,n]的每个状态 for(int i = 2; i <= n; i++) { for(int j = 1; j <= i - 1; j++) { // 求出两种转移情况(乘积个数为2和2以上)的最大值 int tmp = Math.max(dp[j] * (i - j), j * (i - j)); dp[i] = Math.max(tmp, dp[i]); } } return dp[n]; } }
动态规划核心思想
动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。
dp五部曲: 1.状态定义(确定dp数组及其下标含义):dp[i]为长度为i的绳子剪成m段最大乘积为dp[i] 2.状态转移(确定递推公式):dp[i]有两种途径可以转移得到 2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个 2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2 两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值 3.初始化(dp数组初始化):初始化dp[1]=1即可 4.遍历顺序:显然为正序遍历 5.返回坐标:返回dp[n]
标签:初始化,遍历,乘积,Offer,int,绳子,dp,14 From: https://www.cnblogs.com/zhz123567/p/17317551.html