代码随想录第三十五天(一刷&&C语言)|整数拆分&&不同的二叉搜索树

发布时间:2023年12月19日

创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。

一、整数拆分

思路:参考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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。