§ Perform DP on measures, not indexes.

• In the problem of longest common subsequence (or any string problem in general), we should conceptually think of the DP state as the length . This gives us a natural base case ( length = 0), as well as makes it much clearer to implement. Compare (1) LCS using indexes as DP state:

int lcs_len(const vector<int> &xs, const vector<int> &ys) {
    // dp[i][j]: LCS between xs[0:i] and ys[0:j] [closed-closed].
    vector<vector<int>> dp(xs.size(), vector<int>(ys.size(), 0));
    int best = 0;
    for(int i = 0; i < xs.size(); ++i) {
        for(int j = 0; j < ys.size(); ++j) {
            if (i > 0 && j > 0) { dp[i][j] = max(dp[i][j], dp[i-1][j-1]); }
            if (i > 0) { dp[i][j] = max(dp[i][j], dp[i-1][j]); }
            if (j > 0) { dp[i][j] = max(dp[i][j], dp[i][j-1]); }
            if (xs[i] == ys[j]) {
                const int prev = i > 0 && j > 0 ? dp[i-1][j-1] : 0;
                dp[i][j] = max(dp[i][j], 1 + prev);
            }
        }
    }
    return dp[xs.size()-1][ys.size()-1];
}

• Versus using length as DP state:

int lcs_len(const vector<int> &xs, const vector<int> &ys) {
    // dp[lx][ly]: LCS between xs[0:lx) and ys[0:ly) [closed-open].
    // lx, ly for ``length of xs, length of ys''
    vector<vector<int>> dp(1+xs.size(), vector<int>(1+ys.size(), 0));
    int best = 0;
    for(int lx = 1; lx <= xs.size(); ++lx) {
        for(int ly = 1; ly <= ys.size(); ++ly) {
            dp[lx][ly] = max(dp[lx-1][ly-1], dp[lx][ly-1], dp[lx-1][ly]);
            if (xs[lx-1] == ys[ly-1]) {
                dp[lx][ly] = max(dp[lx][ly], 1 + dp[lx-1][ly-1]);
            }
        }
    }
    return dp[xs.size()][ys.size()];
}

• Length is more natural, because length=0 actually corresponds to a degenerate case.
• In general, whenever performing DP, you will likely always need extra states for the degenerate case. It's a good thing to have this, since it simplifies a TON of the implementation work!