LIS(最長増加部分列)を全探索，メモ化でといた

アリ本にのっていたLISを全探索，メモ化でも解いたので覚え書き

LISは与えられた配列をaとするとi>jかつa[i]>a[j]を満たす部分列のこと

DPバージョン

dp[i]はiより前のjの中で制約(i>j かつ a[i]>a[j])を満たすdp[j]の一番大きい値の+1となる．
例えば，a = {4, 2, 12, 3, 1, 5, 8, 10, 3, 9, 2, 11}でi=5のとき
jの範囲は0<=j<5までなので，dp[0<=j<5]のなかで制約を満たす一番大きい値+1がdp[5]の値となる
つまり，今回の場合はa[5]=5なので制約を満たすのはdp[j=3] (a[5] > a[3])となる．よって，dp[3]=2なのでdp[5]=dp[3]+1=3となる．

import java.util.*;

public class LIS3 {
  public static int INF = 10000000;
  public static int N = 12;
  public static int[] a = {4, 2, 12, 3, 1, 5, 8, 10, 3, 9, 2, 11};
  public static int[] dp = new int[N];

  public static void main(String[] args) {
    int ans = 0;
    for (int i = 0; i < N; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (a[i] > a[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      ans = Math.max(ans, dp[i]);
    }
    System.out.println(ans);
  }
}

全探索(深さ優先)バージョン

全探索バージョンはdp配列作らないだけで出来た．
dpとやってることは同じ．
dp[i]がdfs(i)になるだけ．
dfsのときもiより小さいjの中を全て探索して制約を満たすj<iの中で最大の値+1となるだけ

import java.util.*;

public class LIS1 {
  public static int INF = 10000000;
  public static int N = 12;
  public static int[] a = {4, 2, 12, 3, 1, 5, 8, 10, 3, 9, 2, 11};

  public static void main(String[] args) {
    int ans = 0;
    for (int i = 0; i < N; i++) {
      ans = Math.max(ans, dfs(i));
    }
    System.out.println(ans);
  }

  public static int dfs(int d) {
    int ans = 1;
    for (int i = 0; i < d; i++) {
      if (a[d] > a[i]) {
        ans = Math.max(ans, dfs(i) + 1);
      }
    }
    return ans;
  }

}

メモ化バージョン

全探索をメモ化しただけ．

import java.util.*;

public class LIS11 {
  public static int INF = 10000000;
  public static int N = 12;
  public static int[] a = {4, 2, 12, 3, 1, 5, 8, 10, 3, 9, 2, 11};
  public static int[] memo = new int[N];

  public static void main(String[] args) {
    Arrays.fill(memo, 0);
    int ans = 0;
    for (int i = 0; i < N; i++) {
      ans = Math.max(ans, dfs(i));
    }
    System.out.println(ans);
  }

  public static int dfs(int d) {
    if(memo[d] != 0) return memo[d];
    int ans = 1;
    for (int i = 0; i < d; i++) {
      if (a[d] > a[i]) {
        ans = Math.max(ans, dfs(i) + 1);
      }
    }
    return memo[d] = ans;
  }

}

間違ってたらごめんなさいですね