代码随想录算法训练营第三十三天 | leetcode:整数拆分,不同二叉搜索树

343. 整数拆分

解题方法

  1. dp[i] = 分拆数字i,可以得到的最大乘积为dp[i]
  2. dp[i] = max(max(i x (i-j), j x dp[i-j]), dp[i]),
    其中i x (i-j)为拆分两个数的情况,j x dp[i-j]为两个以上的数,j * dp[i - j]相当于是拆分(i - j),对这个拆分不理解的话,可以回想dp数组的定义
  3. 因为2 <= n <= 58, 所以初始化 dp[2] = 1即可
  4. 遍历顺序:dp[i] 是依靠 dp[i - j]的状态,所以遍历i一定是从前向后遍历,先有dp[i - j]再有dp[i]。

code

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function integerBreak($n) {
        $dp = [];
        $dp[2] = 1;
        for($i = 3; $i <= $n; $i++){
            //每次拆分都需要靠近i/2才有可能获得最大
            for($j = 1; $j <= $i/2; $j++){
                $dp[$i] = max($dp[$i], max($j * ($i - $j), $j * $dp[$i - $j]));
            }
        }
        return $dp[$n];
    }
}

复杂度

时间复杂度

O(m x n)

空间复杂度

O(m x n)

Problem: 96. 不同的二叉搜索树

解题方法

  1. dp[i]: 当有i个节点时,最多能有dp[i]种不同的二叉搜索树
  2. 推导递推公式(超级难点,根本想不到):
    • dp[i] = 累计当头结点为1-n的情况。 举例:n=3。dp[i] = 头结点=1的数量的情况 + 头结点=2的情况 + 头结点=3的情况。
    • 二叉树确定头结点的情况下有多少种组合方式呢,是等于左子树的组合方式 * 右子树的组合方式。
    • 即:
      • 当n=3,头结点=1时: 左子树节点为空 = 0:组合方式只有1种,右子树节点为2: 有2种组合方式。总共有1 x 2种组合方式
      • 当n=3,头结点=2时:左子树节点 = 1 组合方式只有1种, 右子树节点数 = 1,组合方式只有1种,;总共有1 x 1一种组合方式
      • 当n=3,头结点=3时:左子树节点 = 2 组合方式有2种, 右子树节点数 = 0,组合方式只有1种;总共有2 x 1一种组合方式
    • 由上可得 :dp[3] = 2 + 1 + 2 = 5;
    • 同时:左子树与右子树也算二叉搜索树,也就是说,左子树和右子树也可以用dp数组表示。
      • 例如当n=3,头结点=1时,左子树节点为空 = 0的情况等于$n=0 即dp[0]的情况。
      • 右子树节点为2 等于$n=2 即dp[2]的情况。
    • 可得:dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0];
      代码随想录算法训练营第三十三天 | leetcode:整数拆分,不同二叉搜索树
    • dp[i] += dp[j - 1] * dp[i - j]; 其中j为头结点,j - 1为左孩子节点,i - j为右孩子节点,j <= i
  3. 初始化dp数组,dp[0] = 1即可。因为当i = j = 1时,用dp[0]就可推导出结果: dp[1] = dp[1-1] * dp[1-1]。
  4. 因为i 依赖与前面的数据,所以遍历顺序是从小到大

code


    /**
     * @param Integer $n
     * @return Integer
     */
    function numTrees($n) {
         $dp = [];
         $dp[0] = 1;
         for($i = 1; $i <= $n; $i++){
             for($j = 1; $j <= $i; $j++){
                 //因为是累计所以这里是+=
                 $dp[$i] += $dp[$j - 1] * $dp[$i - $j];
             }
         }
         return $dp[$n];
    }
}

复杂度

时间复杂度

O(n^2)

空间复杂度

O(n)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!