代码随想录第三十五天(一刷&&C语言)|整数拆分&&不同的二叉搜索树
2023-12-19 00:53:47
创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。
一、整数拆分
思路:参考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]为1
dp[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]设为1
dp[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];
}
文章来源:https://blog.csdn.net/qq_57729144/article/details/135072945
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!