1. Dynamic Programming

• 1. Dynamic Programming
  • 1.1. Tutorial
    • 1.1.1. Introduction
      • 1.1.1.1. Overlapping Subproblems
        • 1.1.1.1.1. Memorization (Top Down)
        • 1.1.1.1.2. Tabulation (Bottom Up)
      • 1.1.1.2. Optimal Substructure
  • 1.2. Steps to Solve Dynamic Programming
    • 1.2.1. Identify Dp problems
    • 1.2.2. Deciding the state
    • 1.2.3. Formulating a relation among the states
    • 1.2.4. Introduction to Algorithms
  • 1.3. Problems
  • 1.4. Reference

1.1. Tutorial

1.1.1. Introduction

First, we need to know 2 properties

1. Overlapping Subproblems
2. Optimal Substructure

1.1.1.1. Overlapping Subproblems

Keyword: memorization

Taking Fibonacci numbers as an example.

public int fib(int n) {
   if ( n <= 1 )
      return n;
   return fib(n-1) + fib(n-2);
}

In this recursion,

1. if we need calculate fib(6), we need to calculate fib(5) and fib(4)
2. if we need fib(5), we need fib(4) and fib(3)

Thus, the fib(4) calculation is duplicated. In order to reuse, we need to store it somewhere.

Generally, we have 2 ways to store it.

1. Memorization (Top Down)
2. Tabulation (Bottom Up)

1.1.1.1.1. Memorization (Top Down)

如果我们使用正常recursion，只不过在recursion之前check是否已经计算过该值对应的结果，那么此种方法称为memorization

  public int fib(int i) {
    if (i < 0) {
      throw new IllegalArgumentException("i needs to be non negative");
    }
    return fibHelper(i);
  }

  private static int fibHelper(int n) {
    if (n <= 1) {
      return n;
    }
    return fibHelper(n - 1) + fibHelper(n - 2);
  }

1.1.1.1.2. Tabulation (Bottom Up)

这个就是正常的dp过程，从0开始推

  public int fib(int n) {
    if (n <= 0) {
      throw new IllegalArgumentException();
    } else if (n <= 2) {
      return 1;
    }
    final int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
  }

1.1.1.2. Optimal Substructure

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

For example, the shortest path problem. If we know point X is on the short path from A to B, we can solve by finding the shortest path from A to X and from X to B.

1.2. Steps to Solve Dynamic Programming

1.2.1. Identify Dp problems

• All the problems that require to maximize or minimize certain quantity or counting problems that say to count the arrangements under certain condition or certain probability problems can be solved by using Dynamic Programming.
• All dynamic programming problems satisfy the overlapping subproblems property and most of the classic dynamic problems also satisfy the optimal substructure property.

1.2.2. Deciding the state

The dimension of the dp array is decided by the number of parameters to decide state

A state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space.

Taking the Knapsack Problem as an example, we can decide the state by using index and weight

1.2.3. Formulating a relation among the states

After making sure what parameter can actually decide the state of the problem, we can think how to solve the problem by knowing the answer of its sub-problem.

Given 3 numbers {1, 3, 5}, we need to tell the total number of ways we can form a number N using the sum of the given three numbers. (allowing repetitions and different arrangements). Total number of ways to form 6 is: 8</p> 1+1+1+1+1+1</p> 1+1+1+3</p> 1+1+3+1</p> 1+3+1+1</p> 3+1+1+1</p> 3+3</p> 1+5</p> 5+1</p>

We can uniquely define the state by using n. Just think, how can we reuse this result to solve a bigger problem

1.2.4. Introduction to Algorithms

Here

1.3. Problems

• 5. Longest Palindromic Substring
• 32. Longest Valid Parentheses
• 87. Scramble_String

1.4. Reference

Geeks for Geeks

背包九讲