求解最长增加子数列

求最长增加子数列是一道经典算法题,其动态规划解法最简单,但是时间复杂度是O(n²)stackoverflow上有一个O(nlogn)解法,很是巧妙:

Now the improvement happens at the second loop, basically, you can improve the speed by using binary search. Besides the array dp[], let’s have another array c[], c is pretty special, c[i] means: the minimum value of the last element of the longest increasing sequence whose length is i.

sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
   if( array[i] < c[1] ) {
  c[1] = array[i]; /*you have to update the minimum value right now*/
  dp[i] = 1;
   }
   else if( array[i] > c[sz] ) {
  c[sz+1] = array[i];
  dp[i] = sz+1;
  sz++;
   }
   else {
  int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
  c[k] = array[i];
  dp[i] = k;
   }
}

关键是理解这个c数组,其下标用来表示增加子数列的长度,而值则是这个长度的增加子数列中结尾元素最小的值。比如有两个相同长度的增加子数列:1,2,31,2,5,则c[3]的值为3,因为一旦将来有4出现,就可以把1,2,3扩展为1,2,3,4,而无法再把1,2,5扩展。完整的Go程序如下:

package main
import (
    "fmt"
    "os"
)

func bSearch(array []int, start int, end int, value int) int {
    for start <= end {
        mid := start + (end-start)/2
        if array[mid] == value {
            return mid
        } else if array[mid] < value {
            if mid+1 <= end && array[mid+1] > value {
                return mid+1
            } else {
                start = mid+1
            }            
        } else {
            if mid-1 >= start && array[mid-1] < value {
                return mid
            } else {
                end = mid-1
            }
        }
    }
    return start
}
func main() {
 //Enter your code here. Read input from STDIN. Print output to STDOUT
    var num int
    _, err := fmt.Scan(&num)
    if err != nil || num == 0{
        os.Exit(1)
    }
    s := make([]int, num)
    m := make([]int, num)
    e := make([]int, num+1)

    for i := 0; i < num; i++ {
        _, err := fmt.Scan(&s[i])
        if err != nil {
            os.Exit(1)
        }
    }

    m[0] = 1
    max := m[0]
    e[1] = s[0]
    for i := 1; i < num; i++ {
        if s[i] < e[1] {
            e[1] = s[i]
            m[i] = 1
        } else if s[i] > e[max] {
            max++
            e[max] = s[i]
            m[i] = max
        } else {
            k := bSearch(e, 1, max, s[i])
            e[k] = s[i]
            m[i] = k
        }
    }

    fmt.Println(max)
}

递归VS非递归

递归是一种很常见的解决问题办法,比如求解Fibonacci数列:

int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

但是递归会导致函数调用栈很深,此外有可能会有很多重复工作。比如求解Fibonacci(4)时,Fibonacci(2)Fibonacci(1)都会被重复求值。看一下非递归解法:

int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        int fi = 0;
        int fj = 1;
        for (int i = 2; i <= n; i++) {
            int temp = fi + fj;
            fi = fj;
            fj = temp;
        }
        return fj;
    }
}

同递归方式相比,用循环迭代的方式取代了函数调用。

最后再看一下wikipedia中关于Binary search tree中查找某一元素的递归和非递归代码。
递归:

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    elif key < node.key:
        return search_recursively(key, node.left)
    else:  # key > node.key
    return search_recursively(key, node.right)

非递归:

def search_iteratively(key, node): 
    current_node = node
    while current_node is not None:
        if key == current_node.key:
            return current_node
        elif key < current_node.key:
            current_node = current_node.left
        else:  # key > current_node.key:
            current_node = current_node.right
    return None

分析求子数组最大值问题

求子数组的最大值是一道经典dynamic programming题,解法如下(参考这里):

public int maxSubArray(int[] A) {
   int newsum=A[0];
   int max=A[0];
   for(int i=1;i<A.length;i++){
       newsum=Math.max(newsum+A[i],A[i]);
       max= Math.max(max, newsum);
   }
   return max;
}

理解这个算法的关键在于:求出数组中以每个元素为子数组的最后一个元素的最大值(上述代码中newsum),这些最大值中的最大者即为解(上述代码中max)。分析如下:从第一个元素A[0]起,newsummax均为A[0]。而对下一个元素A[1],以A[1]为子数组的最后一个元素的最大值或者是A[0]+A[1]A[0]大于0),或是A[1],取两者最大值。接下来再看A[2],以A[2]为子数组的最后一个元素的最大值是A[0]+A[1]+A[2]A[1]+A[2]A[2]三者之间的最大值。以此类推。。。

由一道题理解DFS算法

GENERATE PARENTHESES这篇文章讲解了如何使用Depth First Search,即DFS算法生成所有有效的括号组合:

void generateParentheses(int n) {
    dfs("", n, n);
}
void dfs(String s, int left, int right) // build the set of solutions using DFS approach
{
    if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
        System.out.println(s);
    if(left > 0) // while we have left parentheses to add, just add them
        dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
    if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
        dfs(s + ")", left, right - 1);
}

由此我也总结了一下DFS算法:
(1)DFS算法也是使用递归来解决问题;
(2)

if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
    System.out.println(s);

上述代码是递归的终止条件。
(3)

if(left > 0) // while we have left parentheses to add, just add them
    dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
    dfs(s + ")", left, right - 1);

每调用一次dfs()函数,会为字符串添加()

if(left > 0) // while we have left parentheses to add, just add them
    dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added

会递归地生成当前位置是(的所有情况。if(right > left)分支则会生成当前位置是)的所有情况。

Memoization和dynamic programming

这篇笔记摘自Tutorial for Dynamic Programming

Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly ‘Remember your Past’ 🙂 . If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem ( referred to as the Optimal Substructure Property ).

There are two ways of doing this.

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.

2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.

Memoization是一种“自顶向下”解决问题的方式,并且顾名思义,它具有保存结果的含义:它把一个问题细化成子问题,如果子问题已经解决,就直接获得结果,反正则解决子问题,并把结果保存起来。
Dynamic Programming则是“自下而上”的解决问题方式,它从处理子问题入手,在解决最终问题之前,保证它的所有子问题都已解决。