Dynamic Programming

Two conditions for dp: optimal substructure + overlapping of subproblem

optimal substructure

A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

overlapping of subproblem

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.

Steps: state + state transition

Fibonacci Numbers

Recursive version

int fibnacci(int i ) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibnacci(i - 1) + fibonacci(i - 2);
}

The total number of nodes in the tree will be the running time. Each internal node has two childrens. The running time will be roughly O(2^n), exponential runtime.

Actually, it is slightly better than O(2^n). The right subtree of any node (fibonacci(i - 2)) is always smaller than the left subtree. O(2^n) is still technically correct.

Dynamic programming version (top-down)/memoization

With small modification, we can tweak this function into O(n) time. We simply cache the results of fibonacci(i) between calls.

int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) return i;
    if (memo[i] == 0) memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    return memo[i];
}

Dynamic programming(bottom-up)/tabulation

First compute fib(1) and fib(0) which are base cases and then compute fib(2)...

int fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    int[] memo = new int[n + 1];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}

Since, in the for loop we just need the previous two numbers, we can get rid of the table and use a few variables instead.

int fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    int first = 0;
    int second = 1;
    int curr = first + second;
    for (int i = 2; i < n; i++ ) {
        curr = first + second;
        first = second;
        second = curr;
    }
    return first + second;
}

note: some people call top-down dynamic programming "memoization" and only use "dynamic programming " to refer to bottom-up work.

动态规划的适用方法

满足下面三个条件之一：

• 求最大值最小值
• 判断是否可行
• 统计方案个数

以下情况是不使用动态规划的情况：

• 求出所有具体的方案
• 输入数据是一个集合而不是序列
• 暴力算法的复杂度已经是多项式级别
  • 动态规划擅长于优化指数级别的复杂度到多项式级别

动态规划就是四个重要的要素：

• 状态
• 方程
• 初始化
• 答案