第九章 动态规划part03● 343.整数拆分 
● 096.不同的二叉搜索树 详细布置 今天两题都挺有难度，建议大家思考一下没思路，直接看题解，第一次做，硬想很难想出来。343. 整数拆分 https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html   
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ96.不同的二叉搜索树 https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html   
视频讲解：https://www.bilibili.com/video/BV1eK411o7QA 

感觉动态规划就是一种递推

day40

整数拆分

 class Solution {public int integerBreak(int n) {//dp[n]是拆分n得到的最大值,拆分的个数>=2int[] dp = new int[n + 1];dp[2] = 1;for(int i = 3 ; i <= n; i++){for(int j = 1; j <= i-j; j++){//j到一半就可以了dp[i] = Math.max(dp[i], Math.max( j * (i - j), j * dp[i-j]));}}return dp[n];}}

---

不同的二叉搜索树

 class Solution {public int numTrees(int n) {//n = 3,头结点为123分情况讨论一下,发现以j为头结点的二叉树是左子树情况*右子树情况int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for( int i = 2; i <= n; i++){for(int j = 1; j <= i; j++){dp[i] += dp[j - 1]*dp[i - j];//左子树dp[j-1]种}}return dp[n];}}

---

感谢大佬分享:

代码随想录-算法训练营day40【动态规划03：整数拆分、不同的二叉搜索树】-CSDN博客