1143. Longest Common Subsequence

class Solution {public:    int longestCommonSubsequence(string text1, string text2) {        std::vector<std::vector<int>> sub(            text1.size() + 1, std::vector<int>(text2.size() + 1, 0));        int i = 0;        int j = 0;        for (int i = 1; i <= text1.size(); i++) {            for (int j = 1; j <= text2.size(); j++) {                if (text1[i - 1] == text2[j - 1]) {                    sub[i][j] = sub[i - 1][j - 1] + 1;                } else {                    sub[i][j] = max(sub[i - 1][j], sub[i][j - 1]);                }            }        }        return sub[text1.size()][text2.size()];    }};

after reading, I started off with first drawing out a table to where first I was thinking Levenshtein distance but it was clear that was not it when i started to actually read the problem.. It was obviously 2D dynamic programming. In my table where I worked it out by hand of how each letter should establish its commonness in the other string by essentially doing a two pointer approach where if some letter was the same, it should add one to such letter position and go through both string.

while (i < text1.size()) {    while (j < text2.size()) {        if (text1[i] == text2[j]) {            sub[i][j] += 1;            j++;        }        i++;    }}

I quickly realized this would only work if the first letter of each string was in common. maybe a search where I would have to first find the first common letter in both strings? however that would easily become its own problem that was apart from the main problem.

So I abandoned that idea and looked at first hint because I was already 10 minutes in. "Try dynamic programming. DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j]." gee, no way... So I looked at my 2d table but this time fully filled in I tried now to do an iterative approach for all character of both strings but was still ultimately stumped. I knew it needed to be something like if some character is equal, then take upper left number and add 1 but I was not sure about the other case. checking hint 2. I realized both parts to dp approach. if the two characters are equal, then take up upper left character and add one signifying that there is a common letter here. And if that is not the case, then find the largest number nearby to carry such to the end so that the largest common subsequence dominates.

base case was 0s before the start of a string. if string was empty then such works out.

This took me a while in the beginning but the hints basically gave away the answer.

Also on further review, I need really get down the fact of "You split up the problem into smaller of the same problems and then rebuild up solving from the base case (usually trivial)" the sub problem here was doing the problem on a smaller subset of both strings.

I was thinking why was this 2D in the first place while other DP problems are 1D. its because of the number of independent variables that are being kept track of. Like in House Robber the question was asking for everything on a one dimension scale. just the index of the house currently being processed. However, this keeps tracks of the ith and jth position of the two strings.