Science Done Right

Dynamic Programming

3 min read

Dynamic Programming Problem

A given problem is a dynamic programming problem if

  • Optimal Substructure: The optimal solution to the problem is formed by optimal solutions to sub-problems.
  • Overlapping Sub-problems: Some of the sub-problems are the same, and therefore if we remember the solution, we only need to solve these sub-problems once.

Chain Matrix Multiplication

Chain Matrix Multiplication Problem

Given a chain of matrices decide which order should we multiply this chain of matrices such that total number of arithmetic operations is minimized.

Proposition

The time complexity of computing is in .

Algorithm

Algorithm Consider a 2-dimensional table , where for is the optimal cost for computing. We do not care about the values for . Then

Misplaced &0, & \quad i=j \\ \min_{i\leq k \leq j-1}\{ m[i,k]+m[k+1,j]+p_{i-1}p_kp_j \} & \quad i<j \end{cases} $$ As the base case we set $𝑚 [𝑖, 𝑗] = 0$ for all $1 ≤ 𝑖 = 𝑗 ≤ 𝑛$. Then loop over $1 ≤ 𝑖 < 𝑗 ≤ 𝑛$ in the order of $j-i$ (i.e. $[1,2] \to [2,3] \to [3,4] \to \dots \to [1,n-1] \to [2,n] \to [1,n]$). Finally, output $m[1,n]$.

Proposition

The time complexity of the above algorithm is in . Proof We spend at most for each entry of the table and iterate half of the table entries which is in . Thus the overall time complexity is in .

Longest Increasing Subsequence(LIS)

Longest Increasing Subsequence Problem

Given an array of size , the task is to find the length of the longest increasing subsequence that is, the longest possible subsequence in which the elements of the subsequence are sorted in increasing order. e.g. The LIS of sequence is .

Algorithm

Let be the length of LIS of . Then can be determined recursively:Then solve it by dynamic programming.

Proposition

The time complexity of the above algorithm is in .

Longest Common Subsequence

Longest Common Subsequence

Given two strings, and , the task is to find the the longest subsequence present in both strings.

Algorithm

Algorithm Let be the length of LCS of and . Then can be determined recursively: where initially and for all indices . Then solve it by 2-dimensional dynamic programming.

lcs1lcs2

Proposition

The table has entries, thus the time complexity is in .

Graph View

Backlinks