本文主要是介绍【动态规划】343. 整数拆分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣链接:343. 整数拆分 - 力扣(LeetCode)
dp数组的含义:dp[i]表示对i拆分,得到最大的积为dp[i]
递推公式:拆成两个数是 j*(i-j),拆成三个及以上是 j*dp[i-j],所以递推公式取两者大值
遍历顺序:从小到大
public int integerBreak(int n) {int[] dp = new int[n+1];dp[1]=0;dp[2]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){//注意这里要把dp[i]也写进去dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
这篇关于【动态规划】343. 整数拆分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!