代码随想录-2023/08/07

动态规划

343.整数拆分

解题思路:

1. 定义dp数组含义, dp[i]代表数字i的拆分最大乘积和
2. 假设一个数字i拆成j, 那么另外一半就是 i-j, 这是拆成两个数字的情况
3. 拆成更多个就是j * dp[i-j], dp[i-j] 就代表了拆分更多个的情况

代码:

class Solution {
    public int integerBreak(int n) {
        // 动态规划 --- dp[i] 代表拆分i能获得的最大乘积
        int[] dp = new int[n 1];
        dp[1] = 1; dp[2] = 1;
        for(int i=3; i<=n; i  ){
            for(int j=1; j < i; j  ){
                dp[i] = Math.max(dp[i], Math.max(j * (i-j), j * dp[i-j]));
            }
            System.out.println(dp[i]);
        }

        return dp[n];
    }
}

96.不同的二叉搜索树

动态规划

1. 定义dp数组含义:dp[i] 代表了i个节点时不同二叉搜索树的数量
2. 假设 n == 5, 因为根节点占了一个,所以此时的不同二叉树数量就对于根节点1->5的情况
3. 对于j 从1 -> 5, 就代表了当根节点为1, 2, 3, 4, 5 的情况
   • j == 1:代表根节点值为1, 此时左子树有0个, 右子树有4个, 数量为dp[0] * dp[4]
   • j == 2:代表根节点值为2, 此时左子树有1个, 右子树有3个, 数量为dp[1] * dp[3]
   • j == 3:代表根节点值为3, 此时左子树有2个, 右子树有2个, 数量为dp[2] * dp[2]
   • j == 4:代表根节点值为4, 此时左子树有3个, 右子树有1个, 数量为dp[3] * dp[1]
   • j == 5:代表根节点值为5, 此时左子树有4个, 右子树有0个, 数量为dp[4] * dp[0]
4. 对于5来说, 其所构成的不同二叉搜索树数量就是这些情况的总和, 即

这篇好文章是转载于：学新通技术网