20 Nov 2016

Recursion to 1 dimensional dynamic programing II

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/11/20/1d-dynamic2.html

This article will show you how to use recursion method solve problem, then easily lead to a 1 dimensional dynamic programing solution.

Unique Binary Search Trees

Leetcode Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, 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

Video explanation

DFS solution

With input is n, 1st step, we have n options, e.g. For is 3, we have 3 options: use 1,2 or 3 as root node. with each option, we got two new sub problem. How many way to form left sub-tree and right sub-tree. Once we solved left sub problem and right sub problem, the number of ways is production of L and R.

Termination condition is, n is 0, empty tree, or n is 1, only one node.

This is very good problem to understanding recursion, unlike previous problems, each step, we have N options, and for each option, we got two new sub-problems.

public int numTrees(int n) {
    return dfs(0, n-1); 
    // return dfsCache(0, n-1); 
    // return dp(n);
}
private int dfs(int L, int R) {
    if (L >= R) return 1;
    int nWay = 0;
    for (int i = L; i <= R; i++) {
        nWay += dfs(L, i-1) * dfs(i+1, R);
    }
    return nWay;
}

DFS + memorize O(n) time complexity solution

private int dfsCache(int L, int R) {
    int[] cache = new int[R-L+1];   
    return dfsCache(L, R, cache);
}
private int dfsCache(int L, int R, int[] cache) {
    if (L >= R) return 1;
    if (cache[R-L] != 0)
        return cache[R-L];
    int nWay = 0;
    for (int i = L; i <= R; i++) {
        nWay += dfsCache(L, i-1, cache) * dfsCache(i+1, R, cache);
    }
    cache[R-L] = nWay;
    return nWay;
}

DP O(n) time complexity solution

Again, Just convert termination status of DFS cache version into initialize status of DP version, options are same.

private int dp(int n) {
    int[] fn = new int[n+1];
    fn[0] = 1; // empty tree
    fn[1] = 1; // 1 node tree
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++)
            fn[i] += fn[j] * fn[i-j-1];
    }
    return fn[n];
}