This post contains solutions for CSES Dynamic Programming Problems. For any feedback, feel free to contact me.

Table of Contents

Dice Combinations

To construct sum \(n\), we have six options:

  • Construct sum \(n-1\) and add a 1.
  • Construct sum \(n-2\) and add a 2.
  • Construct sum \(n-3\) and add a 3.
  • Construct sum \(n-4\) and add a 4.
  • Construct sum \(n-5\) and add a 5.
  • Construct sum \(n-6\) and add a 6.

Hence the number of ways to construct sum \(n\) is the sum of the number of ways to construct sum \(n-1\), \(n-2\), \(n-3\), \(n-4\), \(n-5\) and \(n-6\).

Now we have the transition \(dp[n] = dp[n-1] + dp[n-2] + dp[n-3] + dp[n-4] + dp[n-5] + dp[n-6]\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    int n; cin >> n;
    vector<ll> a(n+1);
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = max(0, i-6); j < i; j++) {
            a[i] += a[j];
        }
        a[i] %= MOD;
    }
    cout << a[n] << endl;
}

Minimizing Coins

Solution 1

We can generalize our solution from the first problem. To construct sum \(x\), we have \(n\) options, i.e. Construct sum \(x-c_i\) and add coin with value \(c_i\).

Now we have the transition \(dp[x] = \min_{i=1}^n(dp[x-c_i] + 1)\).

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e9 + 7;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<int> dp(x + 1, MAX);
  dp[0] = 0;
  for (int i = 1; i <= x; i++) {
    for (auto& c : a) {
      if (i - c >= 0) dp[i] = min(dp[i], dp[i - c] + 1);
    }
  }

  cout << (dp[x] == MAX ? -1 : dp[x]) << endl;
}

Solution 2

The other subproblem is not solving for a smaller sum firs, but solving for a smaller number of coins first.

When we add a coin with value \(c_i\) into our set, we have \(dp[x] = \min(dp[x], dp[x-c_i] + 1)\). This is because we can always add a coin with value \(c_i\) to a set of coins that can construct sum \(x-c_i\) to get sum \(x\).

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e9 + 7;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<int> dp(x + 1, MAX);
  dp[0] = 0;
  for (auto& c : a) {
    for (int i = 1; i <= x; i++) {
      if (i - c >= 0) dp[i] = min(dp[i], dp[i - c] + 1);
    }
  }

  cout << (dp[x] == MAX ? -1 : dp[x]) << endl;
}

Note

Note that the code for both solutions are the same with just two lines swapped. Can you always do so? Look at the next problem.

Coin Combinations I (unordered) and II (ordered)

This problem is very similar to the previous problem. The only difference is that we store the number of ways instead of the minimum number of coins.

The transition is \(dp[x] = \sum_{i=1}^n(dp[x-c_i])\).

However, the order of the for loops matter.

If we use the first solution (for 1 to x: for coin i:), the subproblem is solving for a smaller sum first. It doesn’t care which coin goes first (2+5 and 5+2 are both counted), hence is used to solve the first problem.

If we use the second solution (for coin i: for 1 to x:), the subproblem is solving for a smaller number of coins first. It cares which coin goes first (Assuming you count coin 2 before coin 5, it will only consider 2+5 and not 5+2), hence is used to solve the second problem.

Coin Combinations I

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<ll> dp(x + 1, 0);
  dp[0] = 1;
  for (int i = 1; i <= x; i++) {
    for (auto& c : a) {
      if (i - c >= 0) dp[i] = (dp[i] + dp[i - c]) % MOD;
    }
  }

  cout << dp[x] << endl;
}

Coin Combinations II

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  vector<ll> dp(x + 1, 0);
  dp[0] = 1;
  for (auto& c : a) {
    for (int i = 1; i <= x; i++) {
      if (i - c >= 0) dp[i] = (dp[i] + dp[i - c]) % MOD;
    }
  }

  cout << dp[x] << endl;
}

Removing Digits

Up until now, we used bottom-up DP (solving for subproblems from 0 till n). Sometimes, it may be easier to use top-down DP (memoization, memorizing our answers for subproblems).

Here’s the trivial way of solving this problem (which should get you a TLE):

#include <bits/stdc++.h>
using namespace std;

int minimumSteps(int n){
	if(n == 0) return 0;

	string s = to_string(n);
	int cur_min = INT_MAX;
	for(char& c : s){
		if(c == '0') continue;
		int digit = c - '0';
		cur_min = min(cur_min, minimumSteps(n - digit) + 1);
	}
	return cur_min;
}

int main(){
	int n; cin >> n;
	cout << minimumSteps(n) << endl;
}

By adding two lines of code and changing one line, we can get a AC solution:

#include <bits/stdc++.h>
using namespace std;

int dp[1000001]; // <--- an array to store our answers
int minimumSteps(int n){
	if(n == 0) return 0;
	if(dp[n]) return dp[n]; // <--- to get our answers if we computed it before

	string s = to_string(n);
	int cur_min = INT_MAX;
	for(char& c : s){
		if(c == '0') continue;
		int digit = c - '0';
		cur_min = min(cur_min, minimumSteps(n - digit) + 1);
	}
	return dp[n] = cur_min; // <--- to store then return our answers
}

int main(){
	int n; cin >> n;
	cout << minimumSteps(n) << endl;
}

Bottom-up method

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n+1, INT_MAX);
  a[0] = 0;
  for (int i = 0; i < n; i++){
    for(int add = 1; add <= 9; add++){
      if(i + add > n) break;
      // check if i + add contains digit add
      string s = to_string(i + add);
      bool contains = false;
      for(char& c : s){
        if(c - '0' == add){
          contains = true;
          break;
        }
      }
      if(contains) a[i + add] = min(a[i + add], a[i] + 1);
    }
  }
  cout << a[n] << endl;
}

Grid Paths

Note that to get to a cell, we can only get to it from the cell above it or the cell to the left of it.

Hence, the transition is \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\), where \(dp[i][j]\) is the number of ways to get to cell \((i, j)\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main(){
    int n; cin >> n;
    vector<string> a(n);
    vector<vector<ll>> dp(n, vector<ll>(n, 0));
    for(int i = 0; i < n; i++) cin >> a[i];

    dp[0][0] = (a[0][0] == '.');
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(a[i][j] != '.') continue;
            if(i > 0) dp[i][j] += dp[i-1][j];
            if(j > 0) dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    }

    cout << dp[n-1][n-1] << endl;
}

Book Shop

This is called knapsack DP.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n,x; cin >> n >> x;
    vector<int> h(n), s(n);
    for(int i = 0; i < n; i++) cin >> h[i];
    for(int i = 0; i < n; i++) cin >> s[i];

    vector<int> dp(x+1, 0);
    for(int i = 0; i < n; i++){
        for(int j = x; j >= 0; j--){
            if(j - h[i] >= 0) dp[j] = max(dp[j], dp[j - h[i]] + s[i]);
        }
    }

    cout << dp[x] << endl;
}

Array Description

We store an array \(dp\), where \(dp[i][j]\) is the number of ways to construct an array of length \(i\), where the last element is \(j\).

If \(a_i\) is defined, then for \(j \neq a_i\), \(dp[i][j] = 0\), while \(dp[i][a_i] = dp[i-1][a_i-1] + dp[i-1][a_i] + dp[i-1][a_i+1]\).

If \(a_i\) is not defined, then \(dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]\) for all \(j\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int main(){
    int n, m; cin >> n >> m;
    vector<int> x(n); for(int i = 0; i < n; i++) cin >> x[i];

    vector<vector<ll>> dp(n, vector<ll>(m+1, 0));
    if(x[0]){
        dp[0][x[0]] = 1;
    } else {
        for(int i = 1; i <= m; i++) dp[0][i] = 1;
    }

    for(int i=1;i<n;i++){
        if(x[i]){
            dp[i][x[i]] = dp[i-1][x[i]];
            if(x[i] > 1) dp[i][x[i]] += dp[i-1][x[i]-1];
            if(x[i] < m) dp[i][x[i]] += dp[i-1][x[i]+1];
            dp[i][x[i]] %= MOD;
        } else {
            for(int j=1;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                if(j > 1) dp[i][j] += dp[i-1][j-1];
                if(j < m) dp[i][j] += dp[i-1][j+1];
                dp[i][j] %= MOD;
            }
        }
    }

    cout << accumulate(dp[n-1].begin(), dp[n-1].end(), 0LL) % MOD << endl;
}

Counting Towers

The subproblem in this case is the number of ways to construct a tower of height \(n-1\). However, there are two cases: one is that the last row is connected, and the other is that the last row is not connected.

Hence, we create a 2D array \(dp[N][2]\), where \(dp[i][0]\) is the number of ways to construct a tower of height \(i\), where the last row is not connected, and \(dp[i][1]\) is the number of ways to construct a tower of height \(i\), where the last row is connected.

For the last row not to be connected,

  • If the previous row was not connected, we can choose to connect the left column, the right column, or both columns. There are 4 ways to do this.
  • If the previous row was connected, the last row must both be unit square blocks. There is only 1 way to do this.

For the last row to be connected,

  • If the previous row was not connected, the last row must be a \(2 \times 1\) block. There is only 1 way to do this.
  • If the previous row was connected, we can choose if we want to connect the final row with the previous row. There are 2 ways to do this.

Hence, \(dp[i][0] = 4 \cdot dp[i-1][0] + dp[i-1][1]\) and \(dp[i][1] = dp[i-1][0] + 2 \cdot dp[i-1][1]\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 1;

int main() {
  vector<array<ll, 2>> dp(MAX); // or ll dp[MAX][2]
  dp[1][0] = dp[1][1] = 1;

  for (int i = 2; i < MAX; i++) {
    dp[i][0] = dp[i - 1][0] * 4 + dp[i - 1][1];
    dp[i][1] = dp[i - 1][0] + dp[i - 1][1] * 2;
    dp[i][0] %= MOD;
    dp[i][1] %= MOD;
  }

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    cout << (dp[n][0] + dp[n][1])%MOD << endl;
  }
}

Edit Distance

This is a very famous problem. It is also called the Levenshtein distance.

The subproblem is the edit distance between the first \(i\) characters of \(s\) and the first \(j\) characters of \(t\).

To compute \(dp[i][j]\), We can either insert a character (from \(dp[i][j-1]\)), delete a character (from \(dp[i-1][j]\)), or replace a character (from \(dp[i-1][j-1]\)). We can also do nothing (from \(dp[i-1][j-1]\) if \(s[i] == t[j]\)).

Hence, \(dp[i][j] = \min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)\) if \(s[i] \neq t[j]\), and \(dp[i][j] = \min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1])\) if \(s[i] == t[j]\).

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s,t; cin >> s >> t;
    vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, INT_MAX));
    dp[0][0] = 0;
    for(int i=0;i<=(int)s.size();i++){
        for(int j=0;j<=(int)t.size();j++){
            if(i > 0) dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
            if(j > 0) dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
            if(i > 0 && j > 0) dp[i][j] = min(dp[i][j], dp[i-1][j-1]+(s[i-1] != t[j-1]));
        }
    }
    cout << dp.back().back() << endl;
}

Rectangle Cutting

Let \(dp[i][j]\) be the minimum number of cuts to cut a rectangle of size \(i \times j\) into unit squares.

If \(i = j\), then \(dp[i][j] = 0\). Otherwise, \(dp[i][j] = \min(\min_{1 \leq k < i} dp[k][j] + dp[i-k][j] + 1, \min_{1 \leq k < j} dp[i][k] + dp[i][j-k] + 1)\).

#include <bits/stdc++.h>
using namespace std;

int dp[501][501];
int minimum_cuts(int a, int b) {
  if (a == b) return 0;
  if (dp[a][b] != 0) return dp[a][b];
  int min_cuts = INT_MAX;
  for (int i = 1; i < a; i++)
    min_cuts = min(min_cuts, 1 + minimum_cuts(i, b) + minimum_cuts(a - i, b));
  for (int i = 1; i < b; i++)
    min_cuts = min(min_cuts, 1 + minimum_cuts(a, i) + minimum_cuts(a, b - i));
  return dp[a][b] = min_cuts;
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << minimum_cuts(a, b) << endl;
}

Money Sums

The subproblem is the number of possible sums using the first \(i\) coins. For \(0\) coins, there is only one possible sum: \(0\).

Let \(S_i\) denote the set of possible sums using the first \(i\) coins. Then, \(S_{i+1} = S_i \cup \{x + a_{i+1} \mid x \in S_i\}\).

Since the problem doesn’t consider \(0\) as a possible sum, we remove that in the end.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  for (int i = 0; i < n; i++) cin >> x[i];

  set<int> possible_sums = {0};
  for (auto& c : x) {
    set<int> possible_sums_with_c = possible_sums;
    for (auto& s : possible_sums) {
      possible_sums_with_c.insert(s + c);
    }
    possible_sums = possible_sums_with_c;
  }

  possible_sums.erase(0);

  cout << possible_sums.size() << endl;
  for (auto& s : possible_sums) {
    cout << s << " ";
  }
  cout << endl;
}

Removal Game

The subproblem is the maximum score that both players can get if the array is \(x_i, x_{i+1}, \dots, x_j\).

Let \(dp[i][j] = {P, Q}\), where \(P\) is the maximum score that the first player (player to move) can get, and \(Q\) is the maximum score that the second player can get if the array is \(x_i, x_{i+1}, \dots, x_j\).

If \(i = j\), then \(dp[i][j] = {x_i, 0}\).

Otherwise, if the first player takes from the left, then what remains is \(dp[i-1][j] = {P_1, Q_1}\), and \(dp[i][j] = {x_i + Q_1, P_1}\).

If the first player takes from the right, then what remains is \(dp[i][j-1] = {P_2, Q_2}\), and \(dp[i][j] = {x_j + Q_2, P_2}\).

Hence, \(dp[i][j] = \max({x_i + Q_1, P_1}, {x_j + Q_2, P_2})\).

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<int> x;

// (l,r) -> (maxScorePlayer1, maxScorePlayer2)
bool processed[5000][5000];
pair<ll, ll> dp[5000][5000];
pair<ll, ll> maxScore(int l, int r) {
  if (l == r) return {x[l], 0};
  if (processed[l][r]) return dp[l][r];
  processed[l][r] = true;

  auto left = maxScore(l + 1, r);
  auto right = maxScore(l, r - 1);
  if (x[l] + left.second > x[r] + right.second) {
    return dp[l][r] = {x[l] + left.second, left.first};
  } else {
    return dp[l][r] = {x[r] + right.second, right.first};
  }
}

int main() {
  int n;
  cin >> n;
  x.resize(n);
  for (auto& i : x) cin >> i;
  cout << maxScore(0, n - 1).first << endl;
}

Two Sets II

As usual, the subproblem is about the first \(n-1\) coins.

Suppose we want to make a split the first \(n-1\) coins into two sets where sum is \(a\) and \(b\) respectively. Then, \(b = \text{sum}(1, 2, \dots, n-1) - a = n*(n-1)/2 - a\). \(b\) is redundant, so we can just consider \(a\).

Hence, the subproblem is the number of ways to make a sum \(s\) using the first \(n-1\) coins.

Let \(dp[i][s]\) be the number of ways to make a sum \(s\) using the first \(i\) coins. Then, \(dp[i][s] = dp[i-1][s-a_i] + dp[i-1][s]\), where we take \(a_i\) from the first set and the second set respectively.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int dp[501][500 * 501 / 2 + 1];  // roughly 250mb
// dp[i][s] = number of ways to make sum s with the first i coins

int waysToMakeSum(int n, int sum) {
  if (sum == 0) return 1;
  if (n == 0 || sum < 0 || sum > n * (n + 1) / 2) return 0;
  if (dp[n][sum]) return dp[n][sum];
  if (dp[n][n * (n + 1) / 2 - sum]) {
    return dp[n][sum] = dp[n][n * (n + 1) / 2 - sum];
  }

  // we have to make {sum, n*(n+1)/2 - sum} with the first n coins
  // we have to make {sum - n, n*(n+1)/2 - sum} or {sum, n*(n+1)/2 - sum - n}
  // with the first n-1 coins
  ll ans = waysToMakeSum(n - 1, sum - n) + waysToMakeSum(n - 1, sum);
  return dp[n][sum] = ans % MOD;
}

int main() {
  int n;
  cin >> n;
  if ((n * (n + 1)) % 4 == 0) {
    ll ans = waysToMakeSum(n, n * (n + 1) / 4);

    // divide by 2:
    // we can't just do ans /= 2 because ans might be odd
    // so we add MOD if ans is odd, then only divide by 2
    if (ans & 1) ans += MOD;
    cout << ans / 2 << endl;
  } else {
    cout << 0 << endl;
  }
}

Precomputation

We can precompute the answers:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;

int dp[501][500 * 501 / 2 + 1];  // roughly 250mb
// dp[i][s] = number of ways to make sum s with the first i coins

int waysToMakeSum(int n, int sum) {
  if (sum == 0) return 1;
  if (n == 0 || sum < 0 || sum > n * (n + 1) / 2) return 0;
  if (dp[n][sum]) return dp[n][sum];
  if (dp[n][n * (n + 1) / 2 - sum]) {
    return dp[n][sum] = dp[n][n * (n + 1) / 2 - sum];
  }

  // we have to make {sum, n*(n+1)/2 - sum} with the first n coins
  // we have to make {sum - n, n*(n+1)/2 - sum} or {sum, n*(n+1)/2 - sum - n}
  // with the first n-1 coins
  ll ans = waysToMakeSum(n - 1, sum - n) + waysToMakeSum(n - 1, sum);
  return dp[n][sum] = ans % MOD;
}

int solve(int n) {
  if ((n * (n + 1)) % 4 == 0) {
    ll ans = waysToMakeSum(n, n * (n + 1) / 4);
    if (ans & 1) ans += MOD;
    return ans / 2;
  }
  return 0;
}

int main(){
    cout << "{";
    for(int i = 1; i <= 500; i++){
        cout << solve(i) << (i==500?"":",");
    }
    cout << "}";
}

Then submitting the code with all the answers already precomputed:

#include <bits/stdc++.h>
using namespace std;

int ans[500] = {0,0,1,1,0,0,4,7,0,0,35,62,0,0,361,657,0,0,4110,7636,0,0,49910,93846,0,0,632602,1199892,0,0,8273610,15796439,0,0,110826888,212681976,0,0,512776583,915017346,0,0,965991877,536015750,0,0,245739109,497111739,0,0,319303648,661531964,0,0,919134122,526597333,0,0,857860749,323065127,0,0,142897738,454622296,0,0,832964922,112945499,0,0,21130483,134912852,0,0,58392205,594756797,0,0,116285762,46020942,0,0,199311883,637852081,0,0,681073029,687587655,0,0,403293621,859161650,0,0,135570834,16951659,0,0,90174435,906443459,0,0,445036292,696064542,0,0,589938798,17765238,0,0,671699270,979144036,0,0,717567569,962408760,0,0,24874238,651719820,0,0,882521441,815306501,0,0,177673311,381523124,0,0,647107433,822743471,0,0,951125976,913762232,0,0,860772858,718799291,0,0,546548485,520899315,0,0,348826222,979465686,0,0,551269897,226367872,0,0,224237396,275455845,0,0,597702194,580526114,0,0,837164670,579854574,0,0,643888367,547744591,0,0,362172782,203753851,0,0,472078730,414960148,0,0,751350256,597996235,0,0,302890488,463389357,0,0,28369705,625260957,0,0,439010166,625343710,0,0,345211145,783212645,0,0,171026155,746149676,0,0,574908810,400819234,0,0,797285006,671068618,0,0,857904807,118539037,0,0,258515519,103887197,0,0,692754470,307691579,0,0,543477917,494845326,0,0,461141061,681627336,0,0,194431224,798222254,0,0,34177070,324550451,0,0,395144714,314224734,0,0,256354567,216295565,0,0,556521816,594547313,0,0,701665484,287171616,0,0,305999810,817725356,0,0,456522567,42456953,0,0,53352478,896195082,0,0,374247344,900048655,0,0,613110673,91338349,0,0,904876664,300880501,0,0,604541603,441166519,0,0,73667549,41483999,0,0,51276243,149197976,0,0,539103967,982253554,0,0,969982399,98482383,0,0,605461327,65785519,0,0,548373331,421491751,0,0,480765781,925355425,0,0,850819946,434384766,0,0,747079619,140715817,0,0,154291092,436737393,0,0,694334366,278298264,0,0,100011200,186925353,0,0,951803656,826521841,0,0,467206470,625245512,0,0,37014692,370302058,0,0,942594593,625802329,0,0,696810018,839447903,0,0,973813010,340829958,0,0,333578000,162910708,0,0,898163184,938735258,0,0,969420912,767331949,0,0,49040853,864361228,0,0,666086921,681324453,0,0,406330883,715350645,0,0,276425302,691275326,0,0,936153559,806887794,0,0,672700998,324056520,0,0,624244157,887151949,0,0,111928807,555201478,0,0,892266330,406976742,0,0,179624853,766709833,0,0,615024703,25276943,0,0,675398735,373735428,0,0,283235362,613728485,0,0,581407804,135760574,0,0,421029356,925084280,0,0,409496848,345330916,0,0,754684998,388429454,0,0,997193850,722803385,0,0,747396848,879532546,0,0,363180870,301109892,0,0,337814331,439172004,0,0,142119927,761228466,0,0,649629227,868002592,0,0,927500726,71856333,0,0,621649641,86464550,0,0,159973467,281964303,0,0,220801847,172221992,0,0,631635476,30971150,0,0,664722592,692804591,0,0,620001363,22371363,0,0,541326371,8514587,0,0,996643776,106479414,0,0,920757401,236457589,0,0,608650075,71857061};

int main(){
    int n;
    cin >> n;
    cout << ans[n-1] << endl;
}

Increasing Subsequence

We add the numbers one by one. Let \(dp[x_i]\) be the length of the longest increasing subsequence ending at \(x_i\) (note that we store using the value, not the index).

Then \(dp[x_i] = \max(dp[x_j] + 1 \mid x_j < x_i)\). Naively, this can be done in \(O(n^2)\), which is not enough, but using a data structure like a sparse segment tree, we can do it in \(O(n \log n)\).

#include <bits/stdc++.h>
using namespace std;

/* Sparse Segment Tree */
template <class S, S (*op)(S, S), S (*e)()>
struct sparseSegtree {
  long long l, r;
  S val;
  sparseSegtree<S, op, e> *left, *right;
  sparseSegtree(long long _l, long long _r) : sparseSegtree(_l, _r, e()) {}
  sparseSegtree(long long _l, long long _r, S _val) : l(_l), r(_r), val(_val) {
    left = right = nullptr;
  }
  void set(long long i, S x) {
    if (l == r) {
      val = x;
      return;
    }
    long long mid = (l + r) / 2;
    if (i <= mid) {
      if (left == nullptr) left = new sparseSegtree<S, op, e>(l, mid, e());
      left->set(i, x);
    } else {
      if (right == nullptr)
        right = new sparseSegtree<S, op, e>(mid + 1, r, e());
      right->set(i, x);
    }
    val = op(left ? left->val : e(), right ? right->val : e());
  }
  S prod(long long ql, long long qr) {
    if (qr < l || r < ql) return e();
    if (ql <= l && r <= qr) return val;
    S sml = e(), smr = e();
    if (left != nullptr) sml = left->prod(ql, qr);
    if (right != nullptr) smr = right->prod(ql, qr);
    return op(sml, smr);
  }
};
/* End: Sparse Segment Tree */

int op(int a, int b) { return max(a, b); }
int e() { return 0; }

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  for (auto& i : x) cin >> i;

  sparseSegtree<int, op, e> st(0, 1e9);
  // st[i] = max length of increasing subsequence ending at VALUE i
  int ans = 0;
  for (int i = 0; i < n; i++) {
    // insert x[i];
    st.set(x[i], max(st.prod(x[i], x[i]), st.prod(0, x[i] - 1) + 1));
    ans = max(ans, st.prod(x[i], x[i]));
  }

  cout << ans << endl;
}

There is also a method which uses Binary Search, which you can view here.

Projects

This is similar to the previous problem. We sort the projects by their deadlines (why?).

Let the final project we do have start time \(s\), end time \(e\), and reward \(r\). Let \(dp[e]\) be the highest reward we can get.

Then \(dp[e] = \max(dp[i] \mid i < s) + r\).

We can use a sparse segment tree.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

/* Sparse Segment Tree */
template <class S, S (*op)(S, S), S (*e)()>
struct sparseSegtree {
  long long l, r;
  S val;
  sparseSegtree<S, op, e>*left, *right;
  sparseSegtree(long long _l, long long _r) : sparseSegtree(_l, _r, e()) {}
  sparseSegtree(long long _l, long long _r, S _val) : l(_l), r(_r), val(_val) {
    left = right = nullptr;
  }
  void set(long long i, S x) {
    if (l == r) {
      val = x;
      return;
    }
    long long mid = (l + r) / 2;
    if (i <= mid) {
      if (left == nullptr) left = new sparseSegtree<S, op, e>(l, mid, e());
      left->set(i, x);
    } else {
      if (right == nullptr)
        right = new sparseSegtree<S, op, e>(mid + 1, r, e());
      right->set(i, x);
    }
    val = op(left ? left->val : e(), right ? right->val : e());
  }
  S prod(long long ql, long long qr) {
    if (qr < l || r < ql) return e();
    if (ql <= l && r <= qr) return val;
    S sml = e(), smr = e();
    if (left != nullptr) sml = left->prod(ql, qr);
    if (right != nullptr) smr = right->prod(ql, qr);
    return op(sml, smr);
  }
};
/* End: Sparse Segment Tree */

struct Project {
  int s, e, r;  // startTime, endTime, reward
};

ll op(ll a, ll b) { return max(a, b); }
ll e() { return 0; }

int main() {
  int n;
  cin >> n;
  vector<Project> projects(n);
  for (int i = 0; i < n; i++) {
    cin >> projects[i].s >> projects[i].e >> projects[i].r;
  }

  // sort by end time
  sort(projects.begin(), projects.end(),
       [](const Project& a, const Project& b) { return a.e < b.e; });

  sparseSegtree<ll, op, e> st(0, 2e9);
  // st[i] = max reward of projects ending at time i
  for (int i = 0; i < n; i++) {
    st.set(projects[i].e, max(st.prod(projects[i].e, projects[i].e),
                              st.prod(0, projects[i].s - 1) + projects[i].r));
  }

  cout << st.prod(0, 2e9) << endl;
}

Elevator Rides

I’m procrastinating

Counting Tilings

Counting Numbers