基础DP

DP需要满足的三个条件(Algorithms design p260)：

1. There are only a polynomial number of subproblems.
2. The solution to the original problem can be easily computed from the solutions to the subproblems. (For example, the original problem may actually be one of the subproblems.)
3. There is a natural ordering on subproblems from "smallest" to "largest," together with an easy-to-compute recurrence.

Fibonacci sequence

三种类型(递归，memorization, dp)的时间比较：

import timeit

# O(1.618^n)
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

# O(n)
def fib_mem(n):
    res = [-1 for i in range(n + 1)]
    def sfib(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        if res[n] == -1:
            res[n] = sfib(n - 1) + sfib(n - 2)
        return res[n]
    return sfib(n)

# O(n)
def fib_dp(n):
    res = [0 for i in range(n + 1)]
    res[1] = 1
    for i in range(2, n + 1):
        res[i] = res[i - 1] + res[i - 2]
    return res[n]

print timeit.Timer("fib(40)", setup="from __main__ import fib").timeit(1)
print timeit.Timer("fib_mem(40)", setup="from __main__ import fib_mem").timeit(1000) / 1000
print timeit.Timer("fib_dp(40)", setup="from __main__ import fib_dp").timeit(1000) / 1000

30.5603938103
1.54750347137e-05
5.25903701782e-06

fib generator

// interface : Genarator.java
public interface Generator<T> {
    T next();
}

// class : Fibonacci.java
public class Fibonacci implements Generator<Integer> {
    private int count = 0;
    public Integer next() {
        return fib(count++);
    }
    public int fib(int n) {
        if (n < 2) return 1;
        return fib(n - 2) + fib(n - 1);
    }

    public static void main(String[] args) {
        Fibonacci gen = new Fibonacci();
        for (int i = 0; i < 10; i++) {
            System.out.print(gen.next() + " ");
        }
    }
}

// class: IterableFibonacci.java 
public class IterableFibonacci extends Fibonacci implements Iterable<Integer> {
    private int n;
    public IterableFibonacci(int count) {n = count;}
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            public boolean hasNext() {
               return n > 0;
            }

            public Integer next() {
                n--;
               return IterableFibonacci.this.next(); // the this instance of the outer IterableFibonacci class
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };

    }

    public static void main(String[] args) {
        for(int i : new IterableFibonacci(10)) {
            System.out.print(i + " ");
        }
    }
}

Weighted Interval Scheduling

p：最后一个不相交的事件
v：每个事件的权重
求事件子集的最大权重值

p = [0, 0, 1, 0, 3, 3]
v = [2, 4, 4, 7, 2, 1]
n = len(v)


def wis(p, v, n):
    if n == 0:
        return 0
    return max(wis(p, v, n - 1), v[n - 1] + wis(p, v, p[n - 1]))

def wis_mem(p, v, n):
    memo = [-1 for i in range(n + 1)]
    def wm(p, v, n):
        if n == 0:
            return 0
        if memo[n] != -1:
            return memo[n]
        memo[n] = max(wm(p, v, n - 1), v[n - 1] + wm(p, v, p[n - 1]))
        return memo[n]
    return wm(p, v, n)


def wis_dp(p, v, n):
    M = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        M[i] = max(M[i - 1], v[i - 1] + M[p[i - 1]])
    return M[n]

print wis(p, v, n)
print wis_mem(p, v, n)
print wis_dp(p, v, n) # 8