(UVa) 1625 - Color Length [對未來DP (?)]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=4500

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 5006;
const int MAX_P = 144;
const int INF = 1e9 + 7;

int dp[MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

int f1[MAX_P],f2[MAX_P],l1[MAX_P],l2[MAX_P];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        string s1,s2;
        cin >> s1 >> s2;
        s1 = " "+s1;
        s2 = " "+s2;
        for (int i=0;MAX_P>i;i++) {
            f1[i] = f2[i] = INF;
            l1[i] = l2[i] = -INF;
        }
        int id=0;
        for (char i:s1) {
            if (f1[i] == INF) f1[i] = id;
            l1[i] = id;
            id++;
        }
        id=0;
        for (char i:s2) {
            if (f2[i] == INF) f2[i] = id;
            l2[i] = id;
            id++;
        }
        int n=s1.size(),m=s2.size();
        for (int i=0;n>i;i++) {
            for (int j=0;m>j;j++) {
                if (!i && !j) {
                    dp[i][j] = 0;
                    continue;
                }
                if (!i) {
                    //from dp[i][j-1]
                    dp[i][j] = dp[i][j-1] + cost[i][j-1];
                    cost[i][j] = cost[i][j-1];
                    //new point
                    if (f1[s2[j]]>i && f2[s2[j]] == j) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l1[s2[j]]<=i && l2[s2[j]] == j) {
                        cost[i][j]--;
                    }
                }
                else if (!j) {
                    //from dp[i-1][j]
                    dp[i][j] = dp[i-1][j] + cost[i-1][j];
                    cost[i][j] = cost[i-1][j];
                    //new point
                    if (f2[s1[i]]>j && f1[s1[i]] == i) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l2[s1[i]]<=j && l1[s1[i]] == i) {
                        cost[i][j]--;
                    }
                }
                else {
                    dp[i][j] = min(dp[i-1][j] + cost[i-1][j], dp[i][j-1] + cost[i][j-1]);
                    cost[i][j] = cost[i-1][j];
                    //new point
                    if (f2[s1[i]]>j && f1[s1[i]] == i) {
                        cost[i][j]++;
                    }
                    //end point
                    if (l2[s1[i]]<=j && l1[s1[i]] == i) {
                        cost[i][j]--;
                    }
                }
            }
        }
        cout<<dp[n-1][m-1]<<endl;
    }
}