(ΦωΦ)＜動的計画法対策講座練習問題 4-1

(ΦωΦ)＜これの答えですよー。目次はここ。

---
問4-1
(ΦωΦ)＜再帰

#include <iostream>
#include <algorithm>
using namespace std;

string s, t;
int n, m;
vector<vector<int>> dp;

// sのi文字分を見た(次にs[i]を見る)
// tのj文字分を見た(次にt[j]を見る)
// そこからの最大数を返す
int rec(int i, int j) {
  int &res = dp[i][j];
  if(res != -1) { return res; }
  // 全部見たので、ここからの最大数は0
  if(i==n && j==m) { return res = 0; } 
  // sは全部見たので、tを1文字進める
  else if(i==n) {
    res = max(res, rec(i, j+1));
  // tは全部見たので、sを1文字進める
  } else if(j==m) {
    res = max(res, rec(i+1, j));
  } else {
    // 同じ文字だったので1を加える。sもtも1文字進める
    if(s[i] == t[j]) {
      res = max(res, rec(i+1, j+1) + 1);
    } else {
      // sだけ1文字進める
      res = max(res, rec(i+1, j));
      // tだけ1文字進める
      res = max(res, rec(i, j+1));
    }
  }
  return res;
}

int main(void) {
  int q; scanf("%d", &q);
  for(int cases=0; cases<q; cases++) {
    cin >> s >> t;
    n = s.size(), m = t.size();
    dp.assign(n+1, vector<int>(m+1, -1));
    int res = rec(0, 0);
    printf("%d\n", res);
  }
  return 0;
}

(ΦωΦ)＜forループその1

#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int>> dp;

int main(void) {
  int q; scanf("%d", &q);
  string s, t;
  int n, m;
  for(int cases=0; cases<q; cases++) {
    cin >> s >> t;
    n = s.size(), m = t.size();
    dp.assign(n+1, vector<int>(m+1));
    for(int i=0; i<=n; i++) {
      for(int j=0; j<=m; j++) {
        if(i==n && j==m) { continue; }
        if(i==n)      { dp[i][j+1] = max(dp[i][j+1], dp[i][j]); }
        else if(j==m) { dp[i+1][j] = max(dp[i+1][j], dp[i][j]); }
        else {
          if(s[i] == t[j]) {
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
          } else {
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]);
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
          }
        }
      }
    }
    int res = dp[n][m];
    printf("%d\n", res);
  }
  return 0;
}

(ΦωΦ)＜forループその2 渡すのではなく貰うようにする

#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int>> dp;

int main(void) {
  int q; scanf("%d", &q);
  string s, t;
  int n, m;
  for(int cases=0; cases<q; cases++) {
    cin >> s >> t;
    n = s.size(), m = t.size();
    dp.assign(n+1, vector<int>(m+1));
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=m; j++) {
        if(i==0 && j==0) { continue; }
        if(i==0)      { dp[i][j] = max(dp[i][j], dp[i][j-1]); }
        else if(j==0) { dp[i][j] = max(dp[i][j], dp[i-1][j]); }
        else {
          if(s[i-1] == t[j-1]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
          } else {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
          }
        }
      }
    }
    int res = dp[n][m];
    printf("%d\n", res);
  }
  return 0;
}

(ΦωΦ)＜forループその3 端のチェックは要らない

#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int>> dp;

int main(void) {
  int q; scanf("%d", &q);
  string s, t;
  int n, m;
  for(int cases=0; cases<q; cases++) {
    cin >> s >> t;
    n = s.size(), m = t.size();
    dp.assign(n+1, vector<int>(m+1));
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=m; j++) {
        if(s[i-1] == t[j-1]) {
          dp[i][j] = dp[i-1][j-1] + 1;
        } else {
          dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
      }
    }
    int res = dp[n][m];
    printf("%d\n", res);
  }
  return 0;
}

(ΦωΦ)＜forループその4 ループカウンタを1ずらす

#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int>> dp;

int main(void) {
  int q; scanf("%d", &q);
  string s, t;
  int n, m;
  for(int cases=0; cases<q; cases++) {
    cin >> s >> t;
    n = s.size(), m = t.size();
    dp.assign(n+1, vector<int>(m+1));
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        if(s[i] == t[j]) {
          dp[i+1][j+1] = dp[i][j] + 1;
        } else {
          dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
      }
    }
    int res = dp[n][m];
    printf("%d\n", res);
  }
  return 0;
}

(ΦωΦ)＜おしまい