처음 생각했던 방법은 dp[i]에 i원을 만들기 위한 동전의 최소 갯수를 저장하는 방식으로 현재 i보다 작은 j원을 순차로 돌며 i - j원 짜리 동전이 있나 확인한 후, dp[i]에는 그 중 가장 작은 값을 넣도록 작성했다.

단순한 dp문제다. 문제의 이동 조건에서 (r+1, c), (r, c+1), (r+1, c+1) 이렇게 3가지를 제시했지만, 사실 상 마지막 (r+1, c+1) 은 신경쓰지 않아도 된다.
왜냐하면 사탕의 갯수는 0 이거나 양수이기 때문에 더 많은 사탕을 가져와야 될 판에 굳이 대각선으로 가로질러 올 필요가 없기 때문이다.

그리디로 풀었을 때 최악의 경우 n * m * k번, 300 * 300 * 10,000 = 900,000,000번 계산하므로 시간초과가 난다.
그래서 dp로 풀어야 한다. 할 줄 알았는데 그리디하게 풀어도 맞는다고 한다.

가장 긴 증가하는 부분 수열 문제에서 dp[]에 길이를 넣었다면 지금 이 문제는 최대값을 넣으면 된다.

만약 i라는 숫자보다 j * j만큼 작은 수 인 i - j * j는 숫자 i의 제곱수의 최소항 갯수 - 1을 가질 것이다.
만약 j * j가 i와 같다면 j * j = i이므로 제곱수의 최소항 갯수가 한개가 된다.
이 과정을 j * j가 i보다 작거나 같을 때까지 반복해 가장 작은 값을 dp[i]에 넣고 i가 n만큼 돌면 dp[n]이 답이 된다.

각 자리수 별로 0 ~ 9까지 숫자들의 등장 가능한 빈도를 세면 된다.
dp로 풀 수 있고 바로 전 자리수에 자신보다 작거나 같은 수가 얼마나 있는지를 dp[i][j]에 저장해나가면 된다.

dp로 접근해서 풀어야 한다.
처음에 생각했던 방법은 dp[i]에 i원을 만들 수 있는 경우의 수를 저장하고, 각 dp[i]에 가지고 있는 동전의 종류(arr[j])원을 뺀 dp[i - arr[j]]를 더해주는 방법으로 풀면 되겠다고 생각했다.