【每日刷题】动态规划-代码随想录动规-8、9

1. 代码随想录-动规8.LC343整数拆分

题目链接
dp数组含义：dp[i]表示拆分i的最大乘积
递推公式：dp[i]= max(j*(i-j), j*dp[i-j], dp[i])
解释：从1遍历j，有两种渠道得到dp[i].
一个是j * (i – j) 直接相乘。
一个是j * dp[i – j]，相当于是拆分(i – j)
为何不拆分j：j是从1开始遍历，拆分j的情况，在遍历j的过程中其实都计算过了
比如：dp[7]拆分3和dp[4]，为什么不拆分3？因为dp[7]拆成1和dp[6]的时候就已经拆3了（1+2+4）
初始化：dp[0] = 0; dp[1] = 0; dp[2] = 1;
遍历终止条件：
拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。
例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数相乘才是最大的，也就是：最差也应该是拆成两个相同的 可能是最大值。
那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。
比如10的拆分最大值最差也是拆成5和5，再拆的细、贴合就是334，但如果从6往后遍历的话，只会越来越加大每个子数之间的差距，不会达到拆成5和5的结果。所以没必要遍历n/2之后的数了。

代码：

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i < dp.length; i++){
            for (int j = 1; j <= i/2; j++){
                int temp = Math.max(j*(i-j), j*dp[i-j]);
                if (temp > dp[i]){
                    dp[i] = temp;
                }
            }
        }
        return dp[n];
    }
}

坑：
内for循环中，j <= i/2;而不是<；
Math.max()里面的参数数量只能是2

2. 代码随想录-动规9.LC96不同的二叉搜索树

题目链接
dp数组含义：dp[i]表示由i个节点组成二叉搜索树的种数
递推公式：
n为2时，头节点为1，有1种方式；头节点为2，有1种方式。

n为3时，种数等于头节点为1的种数+头节点为2的种数+头节点为3的种数
头节点为1的种数 = dp[0] * dp[2]，左子数无，右子树2个节点
头节点为2的种数 = dp[1] * dp[1]，左子树1个节点，右子树1个节点
头节点为3的种数 = dp[2] * dp[0]，左子树2个节点，右子树无

所以，公式为：
dp[i] += dp[j-1] * dp[i-j];
从1遍历j，直到i
初始化：dp[0] = 1; dp[1] = 1;

代码：

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++){
            for (int j = 1; j <= i; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[dp.length-1];
    }
}

思考：学会分类很重要。分对类了事半功倍！