→とりあえずメモ化再帰してみよう。
できた。
→漸化式漸化式...
できた。
import java.util.Scanner; public class Main { static int n; static int m; static String s; static String t; static int[][] dp; static int[][] dp0; public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); int K = stdIn.nextInt(); for(int ii = 0; ii < K; ii++) { String sS = stdIn.next(); String tS = stdIn.next(); n = sS.length(); m = tS.length(); s = sS; t = tS; dp = new int[n+1][m+1]; dp0 = new int[n+1][m+1]; for(int i = 0; i < n+1; i++) { for(int j = 0; j < m+1; j++) { dp[i][j] = -1; } } int ans = sorv(0,0); System.out.println(ans); //メモ化再帰 ans = sorv(); System.out.println(ans); //動的計画法 } } //--- メモ化再帰 ---// static int sorv(int i, int p) { if(dp[i][p] != -1) return dp[i][p]; if(i == n || p == m) { return 0; } int tmp = t.indexOf(Character.toString(s.charAt(i)), p); int c0 = 0; int c1 = 0; if(tmp >= 0) { c0 = sorv(i+1,tmp+1)+1; c1 = sorv(i+1,p); } int c2 = sorv(i+1,p); int max = c0; if(max < c1) max = c1; if(max < c2) max = c2; dp[i][p] = max; return max; } //--- 動的計画法 ---// static int sorv() { for(int i = n-1; i >= 0; i--) { for(int j = 0; j < m; j++) { int tmp = t.indexOf(Character.toString(s.charAt(i)), j); if(tmp < 0) dp0[i][j] = dp0[i+1][j]; else { int c0 = dp0[i+1][j]; int c1 = dp0[i+1][tmp+1]+1; dp0[i][j] = (c0 < c1)?c1:c0; } } } return dp0[0][0]; } }