In bottom-up solution,

"If the character s1[i] matches s2[j], the length of the common subsequence would be one plus the length of the common subsequence till the i-1 and j-1 indexes in the two respective strings," which is intuitive.

But the actual code checks for s1[i-1] ==s2[i-2]:

for i in range(1, n1+1): for j in range(1, n2+1): if s1[i - 1] == s2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1]

When i try to write it as follows, I get 4 instead of 5 for "passport"/"ppsspt"

max_length = 0 for s1_idx in range (1, len(s1)): for s2_idx in range(1, len(s2)): if s1[s1_idx] == s2[s2_idx]: dp[s1_idx][s2_idx] = 1 + dp[s1_idx-1][s2_idx-1] else: dp[s1_idx][s2_idx] = max(dp[s1_idx-1][s2_idx], dp[s1_idx][s2_idx-1])

max_length = max(max_length, dp[s1_idx][s2_idx])

return max_length

Is there a way to check for s[i][j] that would still give the right answers?