So I was solving the DP problems over at cses.fi/problemset. and I came cross a certain conundrum.

I wrote a code for https://cses.fi/problemset/task/1636/ and when I submitted it, it passed all test cases, except for a Time Limit Exceeded on two of them. I found an editorial on CodeForces and tried to figure out where I went wrong. The code was the same as mine only with the difference that instead of using dp[i][j], their code used dp[j][i], basically transposing the dp array in my code. There were other minor differences, turns out they didn't matter.

Here is my code:

#include <iostream>
#include <limits>
#include <vector>
 
using namespace std;
 
#pragma region util
#define read(args...)                                                          \
    int args;                                                                  \
    _read(args);
 
template <typename Arg> void _read(Arg &&arg) { cin >> arg; }
 
template <typename Arg, typename... Args>
void _read(Arg &&arg, Args &&...args) {
    cin >> arg;
    _read(args...);
}
 
#define readv(vec, n)                                                          \
    vector<int> vec(n);                                                        \
    for (int i = 0; i < n; i++) {                                              \
        cin >> vec[i];                                                         \
    }
 
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rev(i, b, a) for (int i = b; i >= a; i--)
 
#pragma endregion
 
const int INF = numeric_limits<int>::max();
const int MOD = 1e9 + 7;
const int MAX_N = 1e6;
 
int dp[MAX_N + 5][100];
 
int main() {
    read(n, x);
    readv(arr, n);
 
    // dp[i][j] is the number of ways we can make `i` using coins [0..j]
    dp[0][0] = 1;
 
    rep(i, 0, arr.size()) { dp[0][i] = 1; }
 
    rep(i, 1, x + 1) {
        rev(j, arr.size()-1, 0) {
            dp[i][j] = (i - arr[j] >= 0 ? dp[i - arr[j]][j] : 0);
 
            if (j + 1 <= arr.size())
                dp[i][j] += dp[i][j + 1];
 
            dp[i][j] %= MOD;
        }
    }
 
    cout << dp[x][0] << endl;
}

And here is the code from the editorial:

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

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int&v : x) cin >> v;

  vector<vector<int>> dp(n+1,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  cout << dp[n][target] << endl;
}

Why was their code faster? Also, I swapped the order of the for loops and changed j to go from 0 to n instead of n to 0. That didn't change much.