백준 11727번, 2xn 타일링2 JAVA풀이

• 점화식 : D[i] = 2 * D[i-2] + D[i-1]

  2x2 타일이 늘어난 것은, 누워진 직사각형 2개가 붙은 D[i-2] 와 동일한 부분임

  // BOTTOM-UP
  public static int bottomUp (int n) {
      d[0] = 1;
      if (n > 0) d[1] = 1;
      for (int i=2; i<=n; i++) {
          d[i] = (2 * d[i-2]) + d[i-1];
          d[i] %= 10007;
      }
      return d[n];
  }
  

  // TOP-DOWN
  public static int topDown (int n) {
      if (n == 0 || n == 1) return 1;
      if (d[n] > 0) return d[n];
    
      d[n] = 2 * topDown(n-2) + topDown(n-1);
      d[n] %= 10007;
    
      return d[n];
  }