C++で2つの数値文字列を同一にするための最小コストの求め方

問題の概要

2つの数値文字列 A と B が与えられたとき、両者を同一の文字列に揃えるために必要な最小コストを求めます。実行できる操作は「文字列から数字を1つ削除する」ことだけで、削除にかかるコストはその数字の値そのものになります。

例えば、A = "6789"、B = "7859" という2つの文字列の場合、A から「6」を、B から「5」をそれぞれ削除すれば2つの文字列が一致します。このとき必要なコストは 5 + 6 = 11 です。

解法のアプローチ：最長共通部分列（LCS）の応用

この問題は、古典的な最長共通部分列（LCS：Longest Common Subsequence）問題の変種として捉えることができます。まず文字列 A と B の LCS を求め、その結果を使って次の式から最小コストを導きます。

最小コスト = CostA + CostB − 2 × lcs_cost

• CostA／CostB：文字列 A・B それぞれに含まれる全ての数字の合計値
• lcs_cost：LCS に含まれる数字の合計値

LCS を構成する文字は2つの文字列に共通して残る部分であるため、削除する必要がありません。つまり、両文字列の総コストから共通部分のコストを2回分差し引けば、削除に必要な最小コストが求まるという仕組みです。

C++での実装例

#include <iostream>
using namespace std;

// メモ化再帰によって、LCSの「コスト」を計算する
int longest_common_subsequence(int dp[101][101], string a, string b, int a_len, int b_len) {
    // DPテーブルの初期化
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            dp[i][j] = -1;
    // どちらかの文字列を読み終えたら終了
    if (a_len < 0 || b_len < 0) {
        return 0;
    }
    // 計算済みならキャッシュを返す
    if (dp[a_len][b_len] != -1)
        return dp[a_len][b_len];
    int res = 0;
    if (a[a_len] == b[b_len]) {
        // 文字が一致：数字の値を加算し、両方のインデックスを進める
        res = int(a[a_len] - 48) + longest_common_subsequence(dp, a, b, a_len - 1, b_len - 1);
    } else {
        // 一致しない場合：どちらか一方をスキップした結果の最大値を取る
        res = max(longest_common_subsequence(dp, a, b, a_len - 1, b_len),
                  longest_common_subsequence(dp, a, b, a_len, b_len - 1));
    }
    dp[a_len][b_len] = res;
    return res;
}

// 文字列内の全ての数字の合計（総削除コスト）を求める
int minCost(string str) {
    int cost = 0;
    for (int i = 0; i < str.length(); i++)
        cost += int(str[i] - 48);
    return cost;
}

int main() {
    string a, b;
    a = "6789";
    b = "7859";
    int dp[101][101];
    cout << "Minimum Cost to make these two numbers identical: "
         << (minCost(a) + minCost(b) - 2 * longest_common_subsequence(dp, a, b, a.length() - 1, b.length() - 1));
    return 0;
}

なお、a[a_len] - 48 という処理は、ASCII コードにおいて数字 '0' が 48 に対応していることを利用した、文字から整数値への変換です。

出力結果

Minimum Cost to make these two numbers identical: 11

計算量について

この実装ではメモ化再帰（トップダウン方式の動的計画法）を採用しています。2つの文字列の長さを N・M とすると、時間計算量および空間計算量はいずれも O(N × M) となり、文字列が長くなっても効率的に動作します。