백준 11052번, 붕어빵 판매하기 JAVA풀이

• D[n] = n개 팔아서 얻을 수 있는 최대 수익

  • 1개를 팔았을 경우

    D[n-1] + P[1]

  • 2개를 팔았을 경우

    D[n-2] + P[2]

  • 최대의 경우 n개

    D[0] + P[n]

  • 점화식 (i개를 팔았을 경우)

    D[n-i] + P[i]

  • D[n] = max(D[n-i] + P[i])

    • 1 <= i <= n

  • D[n] 한칸을 채우는데 O(n)

  • 붕어빵 판매하기의 시간 복잡도는 O(n^2)

  //BOTTOM-UP
  public static int bottomUp (int n) {
      DP[0] = 0;
      for (int i=1; i<=n; i++) {
          for (int j=1; j<=i; j++) {
              DP[i] = Math.max(DP[i], DP[i-j] + P[j]);
          }
      }
      return DP[n];
  }