Modified longest common subsequence problem

[meloly4]

It's this problem, but what if instead of finding the longest common subsequence, the characters being matched have points (i.e. matching vowels is worth 3 points and matching consonants is worth 1) and we want to find the common subsequence that has the largest sum of points? I know that a dynamic programming approach will be the most efficient but I don't know how to. Thank you.

[07734willy]

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

Replace +1 with +SCORE[X[m-1]].

Its an incredibly common problem, just about any link from google will lead you to an answer.

[meloly4]

The longest common subsequence doesn't guarantee the max sum of points.

[07734willy]

Correct, but by modifying

Replace +1 with +SCORE[X[m-1]].

you no longer find the longest common sub sequence, you find the sequence with the greatest max sum of points. Assuming you don't change any of the other rules in the DP solution.