手机运用网站,网站开发项目付款方式,做衣服的网站推荐,重庆口碑最好的装修公司第九章 动态规划 343.整数拆分96.不同的二叉搜索树代码随想录文章详解 343.整数拆分
dp[i]表示拆分i得到的最大乘积#xff0c;对于[1,i)范围内的任意数j#xff0c;dp[i]最大#xff0c;即max(j与(i-j)乘积, j与(i-j)最大拆分结果dp[i-j]) 边界情况#xff1a;对于一个正… 第九章 动态规划 343.整数拆分96.不同的二叉搜索树代码随想录文章详解 343.整数拆分
dp[i]表示拆分i得到的最大乘积对于[1,i)范围内的任意数jdp[i]最大即max(j与(i-j)乘积, j与(i-j)最大拆分结果dp[i-j]) 边界情况对于一个正整数将其拆分为至少两个正整数之和dp[0]dp[1]没有意义 在遍历过程中当ji/2时相当于重复前面的遍历过程所以j取[1,i/2],记录遍历过程中第i轮的最大值dp[i]
func integerBreak(n int) int {dp : make([]int, n1)for i : 2; i n; i {for j : 1; j i/2; j {dp[i] max(dp[i], j*(i-j), j*dp[i-j])}}return dp[n]
}96.不同的二叉搜索树
对于一棵二叉搜索树左子树小于右子树因此遍历1到n范围内的任意数字i将其作为根节点递归构建左子树[1,i-1]与右子树[i1,n] dp[i]表示以i为根节点构建BST树的所有情况 边界情况空节点或只有一个根节点只有一种情况dp[0] 1dp[1] 1
func numTrees(n int) int {dp : make([]int, n1)dp[0], dp[1] 1, 1for i : 2; i n; i {for j : 1; j i; j {dp[i] dp[j-1] * dp[i-j]}}return dp[n]
}递归超时了
func numTrees(n int) int {if n 0 || n 1 {return 1}res : 0for i : 1; i n; i {leftres : numTrees(i - 1)rightres : numTrees(n - i)res leftres * rightres}return res
}代码随想录文章详解
343.整数拆分 96.不同的二叉搜索树
