LeetCode: Maximum Value of K Coins From Piles

https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/

DP에 대한 더욱 더 깊은 이해를 위해 리트코드의 문제들을 풀려고 한다.

해당 문제는 메모리제이션을 활용하여 풀었어야 했던 문제였다.

1. 다음 동전주머니로 이동시킨다.
2. 다음 동전주머니로 이동시키지 않을 떄
2-1. 0부터 뽑아야 하는 동전개수 만큼 반복문을 돌린다.
2-1-E. 동전개수보다 동전주머니의 길이가 작을 수도 있기에 반복문의 끝조건을 MIN(동전개수, 동전주머니의 길이)로 잡는다.
2-2. 반복문에 순회하는 동전주머니의 인덱스에 해당하는 값을 더한다.
2-3. 더하면서 해당 DP[pile][coin] = MAX(DP[pile][coin], DP[pile-1][coin] + 더한 값)을 통해 비교한다

단순히 문제를 보았을 땐 dfs를 통해 완전탐색을 노렸겠지만 시간을 고려한 생각들을 해야하는 것 같기에 리트코드를 꾸준하게 풀어보기로 했다.

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int dp[][] = new int[n + 1][k + 1];
        for (int pile = 1; pile <= n; pile++) {
            for (int coin = 0; coin <= k; coin++) {
                int currentSum = 0;
                for (int currentCoin = 0; currentCoin <= Math.min((int)piles.get(pile - 1).size(), coin); currentCoin++) {
                    if (currentCoin > 0) {
                        currentSum += piles.get(pile - 1).get(currentCoin - 1);
                    }
                    dp[pile][coin] = Math.max(dp[pile][coin], dp[pile - 1][coin - currentCoin] + currentSum);
                }
            }
        }
        return dp[n][k];
    }
}