本文主要是介绍Day38 代码随想录(1刷)动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
343. 整数拆分
96. 不同的二叉搜索树
343. 整数拆分
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。提示:
2 <= n <= 58
状态：完成
思路：这题一开始我就知道这个数学方法就是能分成多少个3就是最大的，如果剩4则最后一个乘4是最大的。动态规划方法，dp数组表示在i时拆开的最大值dp[i]，所以dp[i]=Math.max(Math.max(dp[i-j]*(j),j*(i-j)),dp[i]);然后最后返回最后一个即可
数学方法：
class Solution {public int integerBreak(int n) {if(n==2) return 1;if(n==3) return 2;return n%3==0?n/3==0?(n/2)*(n-n/2):(int)Math.pow(3,n/3):n/3-1==0?(n/2)*(n-n/2):n%3==1?(int)(Math.pow(3,n/3-1)*(n%3+3)):(int)(Math.pow(3,n/3)*(n%3));}
}动态规划方法：
class Solution {public int integerBreak(int n) {int[] arr=new int[n+1];arr[2]=1;for(int i=3;i<n+1;i++){for(int j=1;j<=i/2;j++){arr[i]=Math.max(Math.max(arr[i-j]*(j),j*(i-j)),arr[i]);}}return arr[n];}
}96. 不同的二叉搜索树
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。示例 1：
输入：n = 3 输出：5示例 2：
输入：n = 1 输出：1提示：
1 <= n <= 19
状态：没做出来
思路：n=1时只有一种情况，n=2时有两种按前序遍历就是1->2，2->1,n=3时有5种，当1作为顶点的时候有两种1->2->3,1->3->2,由此可以发现左子树有两个节点时的顺序情况跟n=2时是一致的所以可以分析出这可以使用动态规划来解决问题，dp[i]=(dp[0]*dp[i-1]+....+dp[i-1]*dp[0]);
class Solution {public int numTrees(int n) {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];}}return dp[n];}
}这篇关于Day38 代码随想录(1刷)动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
