Algorithm

96.unique-binary-search-trees

Description:

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Appropriate Answer (Dynamic Programming):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<?php

namespace LeetCode\UniqueBinarySearchTrees;

class Solution
{
    /**
     * @var array
     */
    private $numOfAnswer = [];

    /**
     * @param int $n
     * @return int
     */
    public function numTrees($n)
    {
        /**
         * 沒有節點的情況有一種可能（空集合）
         */
        $this->numOfAnswer[0] = 1;

        /**
         * 1個節點的情況有一種可能（一個點）
         */
        $this->numOfAnswer[1] = 1;

        for ($i = 2; $i <= $n; $i++) {
            $this->count($i);
        }

        return $this->numOfAnswer[$n];
    }

    /**
     * @param int $n
     * @return void
     */
    private function count($n)
    {
        /**
         * 先取出一個節點當root
         */
        $num = $n - 1;

        /**
         * 1. 左節點的數量 + 右節點的數量 = $num
         * 2. 總和 = 左節點數量的所有可能 * 右節點數量的所有可能
         */
        $result = 0;
        for ($i = 0; $i <= $num; $i++) {
            $result = $result + $this->numOfAnswer[$i] * $this->numOfAnswer[$num - $i];
        }

        $this->numOfAnswer[$n] = $result;
    }
}

  • Time Complexity: O(n)

ʕ •ᴥ•ʔ：DP Program的思考方式還須多多練習。