动态规划问题(三)

一 填表法，计算不同二叉搜索树的数量

给定一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

本题可以假设 n 个节点有排序，因为互不相同，存在等价性。
也就是：

• 如果 有两组不同的节点，数量相同，那么它们组成的二叉搜索树的种类是一样的。

对于一种特殊的情况: 有三个不同节点。
那么分别选定 , , , 以他们为根节点的二叉搜索树被划分成两部分

• 情况1 空集和
• 情况2 分成 和
• 情况3 和 空集
  所有的种类为 三种情况的加和，其中情况1 和情况 3 是等价的。而情况是两种子情况的乘积。

推到一般情况，我们发现问题可以被分解成一系列字问题
表达成数学递推式子为

简而言之， 能决定
因而可以逐步求得 —— 如果使用自顶向下递归，将会产生大量的重复子问题，计算效率极慢。但是用自底向上逐步求解，则每个 可以在期望运行时间 内求得，整个算法的效率时间界是
C++ 代码

int num_of_trees(int n) {
        vector<int> table(n + 1);
        table[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int s = 0;
            for (int j = 0; j < i; ++j) {
                s += table[j] * table[i - j - 1];
            }
            table[i] = s;
        }
        return table[n];
    }

注意这个结果在n增长到20左右时会膨胀得特别快，因而 32 位整数可能无法容纳最后的结果。实际应用中需要严格考虑数据类型的表达范围。

丑数

丑数是只包含质因数 2、3 和/或 5 的正整数。1 定义为丑数。
我们怎么推演出丑数表。
丑数表的前 10项为：

1, 2, 3, 4, 5, 6, 8, 9,10, 12, 15, 16, 18, ... 

一种用最小堆的方案是，每次采取一定的规律生成2, 3 ,5 的倍数，存储起来，由于“这个规律”不太能保证绝对的大小顺序，因而使用最小堆存取新丑数。
一边存，一边取，迭代 n 次后我们计算出来 第n 个丑数
算法要保证每次都有数可取, 并且下一个丑数能及时存入堆中。

我们稍微推演一下：

• 第一步，将 作为第一个丑数
• 第二步，分别将 的 2, 3 ,5 倍 , 它们一定都是丑数，加入到堆中，然后从堆中取出最小的数 2 作为第 2 个丑数， , 此时堆中仍有 [3, 5] 两个数
• 第三步， , 将 入堆，此时堆中有 [3, 4, 5, 6, 10]， 取出最小的数 3 作为第3个丑数
• 第四步， 将 入堆，此时堆中有 [4, 5, 6, 6, 9, 10, 15] 我们发现出现了重复数 6，因此需要有一个哈希表来去重，去重以后，堆中元素为 [4, 5, 6, 9, 10, 15]
  ... 以此类推。

很明显，上面这种入堆的方案不会遗漏任何丑数。其次，通过n 步之后，堆中的丑数数量远远大于 n 个，但是不超过 3n个(因为有一些重复数) ， 并且 n 次迭代后， 前 n 个丑数已经出现。因为下一次最小的丑数是 的两倍 。

这个算法可以在 O(nlogn) 的复杂度下计算出第 n 个丑数。

算法多计算了大概 3 倍规模的丑数

int nthUglyNumber(int n) {
      vector<int> factors{2, 3, 5};
      unordered_set<long> table; // 哈希表用于去重
      priority_queue<long, vector<long>, greater<long> > heap; // std库的默认堆是最大堆，因此需要声明 greater<long> 参数
      table.insert(1L);
      heap.push(1L);
      int ugly_n = 0;
      for (int i = 0; i < n; ++i) {
          ugly_n = heap.top();
          heap.pop();
          for (int factor: factors) {
              long next = (long)ugly_n * factor;
              if (table.count(next) == 0) {
                  table.insert(next);
                  heap.push(next);
             }
         }
     }
     return ugly_n;
}

动态规划解法
我们分别列出 2,3,5 的倍数列表
2n —— [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,....]
3n —— [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, ...]
5n —— [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, ...]
列表中有些数是丑数，有些不是，但是，理论上，所有的丑数都会至少出现在其中之一上。
我们从上面的列表中筛选出丑数，得到下面的丑数表
2n A —— [2,4,6, 8,10,12,16,18,20,24,30, ....]
3n B—— [3,6,9,12,15,18,24,27,30,36,...]
5n C—— [5,10,15,20,25,30,40, 45, 50, ....]

假设我们知道了第 n 个丑数是 ， 那么第 n + 1 个丑数 就是 三个数组中没有被用过的最小的数。
用三个循环子p1, p2, p3 分别代表三个数组中当前元素，对于每个 数组，必然有

采用动态规划的思想，假设我们已经得到了 前面的 n - 1 个丑数 ，并且当前循环子分别落在 p1, p2, p3 的位置，由上面的推导，我们知道丑数 和 中的一个或多个相等，把和 相等的循环子向后移动一格(有可能要移动两个或三个), 不妨设 与 相等。

那么 ，有

其它几种情况

写成C++代码

int nthUglyNumber(int n) {
    int i1 = 1, i2 = 1, i3 = 1;
    vector<int> dp(n + 1);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int _2x = dp[i1] * 2;
        int _3x = dp[i2] * 3;
        int _5x = dp[i3] * 5;
        int x = min(min(_2x, _3x), _5x);
        dp[i] = x;
        if (x == _2x) {
            i1++;
        }
        if (x == _3x) {
            i2++;
        }
        if (x == _5x) {
            i3++;
        }
   }
   return dp[n];
}

动态规划的方法显然有着更好地时间界。因而它是一种更优的方案。

我们可以用它解决一类这种问题： 在几个分类里以此挑选“最优”选项的问题。