本文主要是介绍代码随想录第三十五天（一刷C语言）|整数拆分不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。
一、整数拆分
思路：参考carl文档。
1、确定dp数组以及下标的含义：分拆数字i，可以得到的最大乘积为dp[i]。
2、确定递推公式：从1遍历j，dp[i]可以由j * (i - j) 直接相乘。也可以由j * dp[i - j](相当于是拆分(i - j))得到。dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))。
3、dp数组的初始化：初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1。
拆分0与1是无意义的。
4、确定遍历的方向：由递推公式知遍历方向为从左到右。
5、举例n为某个数的时候，推到dp数组。
ledcode题目：https://leetcode.cn/problems/integer-break/
AC代码：
//初始化DP数组
int *initDP(int num) {int* dp = (int*)malloc(sizeof(int) * (num + 1));int i;for(i = 0; i < num + 1; ++i) {dp[i] = 0;}return dp;
}//取三数最大值
int max(int num1, int num2, int num3) {int tempMax = num1 > num2 ? num1 : num2;return tempMax > num3 ? tempMax : num3;
}int integerBreak(int n){int *dp = initDP(n);//初始化dp[2]为1dp[2] = 1;int i;for(i = 3; i <= n; ++i) {int j;for(j = 1; j < i - 1; ++j) {//取得上次循环:dp[i]，原数相乘，或j*dp[]i-j] 三数中的最大值dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);}}return dp[n];
}二、不同的二叉搜索树
思路：参考carl文档。
1、确定dp数组及其下标的含义：1到i为节点组成的二叉搜索树的个数为dp[i]。
2、确定递推公式：dp[i] += dp[j - 1] * dp[i - j] ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量。
3、dp数组的初始化：空节点也是一棵二叉树，也是一棵二叉搜索树。初始化dp[0] = 1。并且防止左右子树相乘出现0值的情况。
4、确定遍历方向：由递推公式知，节点数为i的状态依靠于 i之前节点数的状态。故遍历i里面每一个数作为头结点的状态，用j来遍历。
5、举例n为某个数的时候dp数组的状态。
lecode题目：https://leetcode.cn/problems/unique-binary-search-trees/description/
AC代码：
//开辟dp数组
int *initDP(int n) {int *dp = (int *)malloc(sizeof(int) * (n + 1));int i;for(i = 0; i <= n; ++i)dp[i] = 0;return dp;
}int numTrees(int n){//开辟dp数组int *dp = initDP(n);//将dp[0]设为1dp[0] = 1;int i, j;for(i = 1; i <= n; ++i) {for(j = 1; j <= i; ++j) {//递推公式：dp[i] = dp[i] + 根为j时左子树种类个数 * 根为j时右子树种类个数dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];
}这篇关于代码随想录第三十五天（一刷C语言）|整数拆分不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
