今天是四十一天,从今天起难度大概就要上来了
class Solution { public int integerBreak(int n) { int[] dp = new int[n+1]; dp[2] = 1; for(int i = 3; i<=n; i++){ for(int j = 1; j< i-1; j++){ dp[i] = Math.max(dp[i], Math.max(j *(i-j), j*dp[i-j])); } } return dp[n]; } }
让dp[]中保留每一个整数能拆分相乘获得的最大值,然后遍历每一种情况来经过不断对比获得最大值。
class Solution { public int numTrees(int n) { int[] dp = new int[20]; dp[0] = 1; dp[1] = 1; dp[2] = 2; for(int i =3; i<=n; i++){ for(int j = i-1; j>=0; j--){ int temp = i -1 -j; dp[i] += dp[j]*dp[temp]; } } return dp[n]; } }
一棵树的节点数量是他的左右两颗子树节点数量相乘
今天是比较难的动态规划。
标签:int,代码,随想录,第四十一,new,public,dp From: https://www.cnblogs.com/catSoda/p/16910203.html