C++で配列を厳密に増加させる：最小操作回数を求める動的計画法

整数を格納する2つの配列 arr1 と arr2 が与えられているとします。ここでの目的は、arr1 を厳密に増加する(狭義単調増加の)配列にするために必要な最小の操作回数を求めることです。なお「操作」とは、インデックス i(0 ≤ i < n)と j(0 ≤ j < m)を選び、arr1[i] = arr2[j] という代入を行うことを指します(n と m はそれぞれ arr1 と arr2 のサイズです)。

どのように操作しても arr1 を厳密に増加させることができない場合は、-1 を返します。

例えば、入力が arr1 = [1,5,3,7,8]、arr2 = [1,3,2,5] の場合、出力は 1 となります。これは、値 5 を 2 に置き換えることで配列が [1,2,3,7,8] となり、厳密に増加する配列になるためです。

解法の考え方

この問題は、ソート+二分探索とメモ化再帰(動的計画法)を組み合わせることで効率的に解くことができます。全体の流れは次のとおりです。

再帰関数 solve() の定義

関数 solve() は、配列 arr1、配列 arr2、インデックス i と j、直前の値 prev、そして2次元配列 dp を引数に取ります。

• i が arr1 のサイズ以上になったら 1 を返します(これが終端条件です)。
• j を、arr2 の j 番目以降の要素のうち prev より大きい最初の要素の位置(upper_bound の結果)に更新します。
• dp[i][j] が -1 以外(すでに計算済み)であれば、その値を返します。
• ret を「arr2 のサイズ + 1」で初期化します。
• prev < arr1[i] の場合：ret := min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp))(現在の要素をそのまま使うケース)
• j < arr2 のサイズの場合：ret := min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp))(現在の要素を arr2 の値に置き換えるケース)
• 最後に dp[i][j] = ret を返します。

メインメソッドでの処理

• 配列 arr2 をソートします。
• n := arr1 のサイズ、m := arr2 のサイズ とします。
• サイズ 2005 × 2005 の2次元配列 dp を定義し、すべての要素を -1 で初期化します(-1 は「未計算」を表します)。
• ret := solve(arr1, arr2, 0, 0, -∞, dp) を呼び出します。
• ret が arr2 のサイズより大きければ -1 を、そうでなければ ret - 1 を返します。

以下の実装例を見ると、理解がより深まるでしょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

入力

{1,5,3,7,8}, {1,3,2,5}

出力

1

アルゴリズムのポイント

• 二分探索による高速化：arr2 を事前にソートしておくことで、upper_bound を利用し「直前の値より大きい最小の置き換え候補」を対数時間で見つけることができます。
• メモ化による重複排除：状態 (i, j) ごとの結果を dp 配列にキャッシュすることで、同じ部分問題の再計算を防ぎ、計算量を大幅に削減できます。
• 戻り値の調整：各置き換え操作で 1 を加算し、終端条件でもさらに 1 を返す構造になっているため、最終的に 1 を引いて実際の操作回数を求めています。