'I will pin your comment if you can optimize this' - about 2 hours later....

beatdown.cpp

#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

void generate_array(std::vector<int>& arr, std::mt19937& gen) {
  std::uniform_int_distribution<> dis(0, 99);
  for (int & i : arr) {
    i = dis(gen);
  }
}
int lcs(const std::vector<int>& a, const std::vector<int>& b) {
  int m = a.size();
  int n = b.size();
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (a[i - 1] == b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}


// define circular data structure that loops over itself
template <typename T, const size_t size> struct circulant{
private:
  std::array<T, size> data = std::array<T,size>();
  size_t circle_index = 0;
public:
  T& operator [] (const size_t i){
    return this->data[(this->circle_index + i) % size];
  }
  void push_back(const T item) {
    this->data[this->circle_index] = item;
    this->circle_index = (this->circle_index + 1) % size;
  }
  T& back() {
    return this->data[(this->circle_index + size - 1) % size];
  }
};
// almost the original code; just take a few references and use a much, much
// better data structure
int lcs2(const std::vector<int>& a, const std::vector<int>& b) {
  const size_t m = a.size();
  const size_t n = b.size();
  circulant<std::vector<int>, 2u> dp;
  dp.push_back(std::vector<int>(n+1, 0.0));
  dp.push_back(std::vector<int>(n+1, 0.0));

  for (size_t i = 1; i <= m; ++i) {
    std::vector<int> & prev = dp[i - 1];
    std::vector<int> & curr = dp[i];
    const int a_ = a[i - 1];
    for (size_t j = 1; j <= n; ++j) {
      curr[j] = a_ == b[j-1] ? (prev[j-1] + 1) : std::max(prev[j], curr[j-1]);
    }
  }
  return dp[m % 2].back();
}

struct Timer {
  using clock = std::chrono::high_resolution_clock;
  using time_unit = decltype(clock::now());
  time_unit start;
  Timer() {
    start = clock::now();
  }
  auto operator()() const {
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double>(end - start).count();
  }
  void reset() {
    start = clock::now();
  }
};

int main(int argc, char* argv[]) {
  if (argc < 3) {
    std::cerr << "Usage: " << argv[0] << " n n_rep" << std::endl;
    return 1;
  }

  int n = std::atoi(argv[1]);
  int n_rep = std::atoi(argv[2]);

  int seed = 12345;
  std::mt19937 gen(seed);
  std::vector<int> a(n);
  std::vector<int> b(n);

  double duration = 0., duration2 = 0.;
  Timer timer;
  int length, length2;
  for (int i = 0; i < n_rep; ++i) {
    generate_array(a, gen);
    generate_array(b, gen);
    [&](){
      timer.reset();
      length = lcs2(a, b);
      duration += timer();
    }();
    // original for comparison
    [&](){
      timer.reset();
      length2 = lcs(a, b);
      duration2 += timer();
    }();
    // check results for validity
    if(length != length2) {
      std::cout << "Unequal result; length: " << length << " length2: " << length2 << "\n";
    }
    else {
      std::cout << "Passed rep: " << i+1 << "\n";
    }
  }
  std::cout << "Time using native C++: " << duration << "s (n_rep=" << n_rep << ")" << std::endl;
  std::cout << "Time using naive C++: " << duration2 << "s (n_rep=" << n_rep << ")" << std::endl;
  return 0;
}

For closest replication use:

 clang++ -std=c++17 -O3 -o beatdown beatdown.cpp

(as you can see, no really magical flags in sight :))