今天是四十一天,从今天起难度大概就要上来了
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]; } }
一棵树的节点数量是他的左右两颗子树节点数量相乘
今天是比较难的动态规划。
原文地址:http://www.cnblogs.com/catSoda/p/16910203.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性