Skip to content

Dynamic Programming

Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problem in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problem, then it is said to have optimal substructure.

If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.

In general, a problem can be solved with dynamic programming if it has:

  • optimal substructure, which means the problem can be solved with one or finite sub-problems;
  • repeated sub-problems, which means that the sub-problems will be solved multiple times.

The optimal substructure defines the relationship between origin problem and its sub-problems, and repeated sub-problems defines the relationship between sub-problems. If optimal substructure is not satisfied, we can not apply the dp method; if repeated sub-problems is not satisfied, we can apply dp, but it has no advange over recursive method.

The general process of applying dp is:

  1. Define the state variable, this is the most flexible step, different state variables has different transmission functions.
  2. Define the transmission function, in this step we iterate all possible selections and get the state with one or more sub-states.
  3. Define the base case, this is necessary when we need more than one sub-problem solutions at the begining but they are not solved.
  4. Solve the problem by calculating the state value needed.

Linear Dp

The main characteristic of linear dp is that the problem is related to its position.

Single Sequence

Longest Increasing Subsequence(LIS)

Given an integer array nums, return the length of the longest strictly increasing subsequence.

The typical solution for LIS is dp, we define:

  1. state dp[i]: the length of LIS which ends with nums[i];
  2. transform: dp[i] = max(dp[j]) + 1, where \(0 \le j < i\) and \(nums[j] < nums[i]\);
  3. base case: dp[0] = 1

And we have the function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int Lis(vector<int>& a) {
  int m = a.size();
  vector dp(m, 1);

  for (int i = 1; i < m; ++i) {
    for (int j = 0; j < i; ++j) {
      if (a[j] >= a[i]) continue;
      dp[i] = max(dp[i], dp[j] + 1);
    }
  }

  return *max_element(dp.begin(), dp.end());
}

Complexity:

  • Time complexity: \(O(N^2)\)
  • Space complexity: \(O(N)\)

The general greedy strategy is that we let the subsequence increasing as slowly as posible. So we define an array d to store the minimum last number of the subsequence of each lenth, d[len] stores the minimum last number of the subsequence of the length i. If current number is greater than d[len], we increase the len and update d[len + 1] to current number; otherwise we use binary search to update d[j] with current number, where dp[j] >= current number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int Lis(vector<int>& a) {
  auto bs = [](auto& d, int tar, int l, int r) {
    while (l < r) {
      int mid = l + (r - l) / 2;
      if (d[mid] < tar) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }

    return l;
  };
  int m = a.size();
  vector d(m + 1, a[0]);
  int len = 1;

  for (int i = 1; i < m; ++i) {
    if (a[i] > d[len]) {
      d[++len] = a[i];
    } else {
      int j = bs(d, a[i], 1, len);
      d[j] = a[i];
    }
  }

  return len;
}

Complexity:

  • Time complexity: \(O(NlogN)\)
  • Space complexity: \(O(N)\)

Other similar problems:

Maximum Sub Array Problems

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Single Sequence that Not Continuouse -- House Robber Problems

When the sequence is not continuous, we need the information of more previous postions.

Single Sequence that Need Two Position

Sometimes we need to consider two positions of subproblem, the state should be dp[i][j] to determine the two position i j of subproblems.

Single Sequence with Another Dimenssion

In addition to position, sometimes we need another variable, for example, the length/times/color. We generally write the state as dp[i][k], where i for the position, k for the additional meanings.

Stock Series Problems

The general description for stock problems is:

you're given an integer array of stock prices: prices, and you can complete at most k transactions.

We define the state as: dp[i][j][x] means that [0:i] prices with j transactions and current state is x(0 or 1, 0 for empty, 1 for hold). And we define that a transaction including buying and selling.

The code can be:

1
2
3
4
5
6
7
8
dp[0][0][1] = -ps[0];
for (int i = 1; i < m; ++i) { dp[i][0][1] = max(dp[i - 1][0][1], -ps[i]); }
for (int i = 1; i < m; ++i) {
  for (int j = 1; j <= k; ++j) {
    dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + ps[i]);
    dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - ps[i]);
  }
}

Package Series Problems

Optimal Problems:

Package Capacity Problems:

Combination Problems:

Other

Double Sequences

In double sequence problems, we define dp[i][j] to represent the solution of s1[0:i] and s2[0:j].

Longest Common Sequence(LCS)

Given two strings text1 and text2, return the length of their longest common subsequence.

Character Matching

Matrix

In matrix problems, we use dp[i][j] to determine the solution of position matrix[i][j], and the subproblem may relate to dp[i - 1][j], dp[i][j - 1] and dp[i - 1][j - 1].

Matrix with Another Dimenssion

Sometimes we also need another variable of subproblems where comes the state dp[i][j][k].

Other

Prefix Sum

Prefix sums are trivial to compute in sequential models of computation, by using the formula \(y_{i} = y_{i - 1} + x_{i}\) to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort, and they form the basis of the scan higher-order function in functional programming languages. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.

Abstractly, a prefix sum requires only a binary associative operator \(\oplus\), making it useful for many applications from calculating well-separated pair decompositions of points to string processing.

Mathematically, the operation of taking prefix sums can be generalized from finite to infinite sequences; in that context, a prefix sum is known as a partial sum of a series. Prefix summation or partial summation form linear operators on the vector spaces of finite or infinite sequences; their inverses are finite difference operators.

There are two types of prefix sum, 1d and 2d:

Sum of a Range or Area

The Range or Area that Less or Equal a Target

Range Dp

In range dynamic programming, the defination and transmission of state are all related to a range.

The typical patterns of this problem is:

1
2
3
4
5
6
7
for (int len = 1; len <= m; ++len) {
  for (int i = 0; i + len - 1 < m; ++i) {
    int j = i + len - 1;

    // dp[i][j] = ...
  }
}

Palindrome Problems

Reverse Order Problems

Other