动态规划为什么这么难?

看到标题你可能会觉得奇怪,因为你刚做完一道非常难的不同路径问题,确实,在 LeetCode 中,这类题被标记为中等难度,但是这道题在动规里真的算简单的啦,毕竟我这种菜鸡花点时间也能做出来,但是,当阁下碰到不同的二叉搜索树这道题,你又该如何应对?难!太难了!哪怕是做过一次,过了一段时间再做,如果没有动笔复现当时的思路,一样是毫无头绪。这次,就好好花时间来解决这道题!

题目描述:

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。(描述如此简短,想必这题应该十分简单吧😁)

二叉搜索树的概念就不过多解释了,一句话简单概括:对于·二叉树中的任意节点,它的左子树中的节点都应小于根节点,它的右子树中的节点都应大于根节点。

参考卡哥:代码随想录 (programmercarl.com)

我们可以使用动态规划的思路来解决这个问题。具体的步骤如下:

  1. 定义一个数组 dp,其中 dp[i] 表示有 i 个节点时可以构成的不同的二叉搜索树的数量。
  2. 初始化 dp[0] = 1,表示空树也是一棵合法的二叉搜索树。
  3. 对于 i = 1 到 n,计算 dp[i] 的值:
    • 遍历 j = 1 到 i,表示当前树的根节点的值为 j。
    • 左子树的节点数为 j-1,右子树的节点数为 i-j。
    • 考虑到二叉搜索树的性质,左子树的节点数可以是 0 到 j-1,右子树的节点数可以是 0 到 i-j-1。
    • 对于每一种划分情况,可以计算左子树和右子树能够构成的不同的二叉搜索树的数量,并将结果累加到 dp[i] 上。
  4. 最后返回 dp[n] 的值,即为能够构成的不同的二叉搜索树的数量。

这个解题思路基于以下观察:

  • 对于一个 BST,如果固定根节点的值 j,那么它的左子树可以有 dp[j-1] 种不同的形态,右子树可以有 dp[i-j] 种不同的形态。所以,以 j 为根节点的 BST 的总数为 dp[j-1] * dp[i-j]。
  • 对于所有可能的根节点值 j,将它们对应的 BST 的总数相加,就得到了 dp[i] 的值。

代码实现:

class Solution {
public int numTrees(int n) {
//初始化 dp 数组
int[] dp = new int[n + 1];
//初始化0个节点和1个节点的情况
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
//对于第i个节点,需要考虑1作为根节点直到i作为根节点的情况,所以需要累加
//一共i个节点,对于根节点j时,左子树的节点个数为j-1,右子树的节点个数为i-j
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}

发现没,死都想不出来的一道题,代码居然如此简单!思路太重要了。