训练营第四十一天 | 343. 整数拆分 ● 96.不同的二叉搜索树

2024-01-10 14:32:25

?343.?整数拆分?

想不到递推公式

代码随想录

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;//初始值；没有dp[0]和dp[1]，因为这个代码用不到
        //从前向后遍历
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i - j; j++) {//j <= i - j是因为i-j后面再遍历没有意义，重复了
                //dp[i - j]是i-j拆分的最大乘积，因为从前向后遍历，所以值在此之前就以得知，比较j * (i - j)和j * dp[i - j]的最大值，之后再与不同j得出的最大dp[i]相比得出最大值;
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

?96.不同的二叉搜索树?

想不到思路

代码随想录

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+1; i++) {
            for(int j = 1; j <= i; j++) {//以j为根节点的情况累加
                dp[i] += dp[j-1] * dp[i-j]; //j-1为左子树的情况，i-j为右子树的情况，相乘为以j为根节点的所有情况，所有j累加为n=i的情况
            }
        }
        return dp[n];
    }
}

?

文章来源:https://blog.csdn.net/Tropic____/article/details/135499710
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。