1 번째 시도

  • memoization으로 풀었다.
  • 점화식
    • dp[i][j] : i 자리수에 숫자 j가 왔을 떄의 오르막 개수 (0 <= j < 9)
      • 1의 자리수에만 0이 올 수 있다. -> dp[1][0] = 1;
    • dp[i][j] = sum(dp[i-1][k]) (j <= k < 9)
    • res = sum(dp[i][j]) + dp[1][0] (단, 1 <= i <= N, 1 <= j < 10)