Leetcode 518) Coin Change 2

31 Jul 2021 in Algorithms

• 순열과 조합 중에 이건 조합이다. 조합을 어떻게 코드로 짜는지 생각하면서 풀어보자.
• 곱하기는 그떄 왜 하려고 했던걸까..?_?
• 그리고 더하기는 왜??_??
• 사고 흐름을 정리해서 그때 했던 실수에 또 빠지지 않도록 해보자.

내 답안

class Solution {
    public int change(int amount, int[] coins) {
        int dp[][] = new int[coins.length+1][amount+1];
        dp[0][0]=1;
        for(int i =1;i<coins.length+1;i++){
            for(int j=0;j<amount+1;j++){
                if(j==0){
                    dp[i][j]=1;
                    continue;
                }
                int cur= j-coins[i-1];
                if(cur>=0){
                    dp[i][j]+=dp[i][cur];
                }
                dp[i][j]+=dp[i-1][j];
            }
        }
        return dp[coins.length][amount];

    }
}

다른 답안

오답

• https://leetcode.com/problems/coin-change-2/discuss/176706/Beginner-Mistake%3A-Why-an-inner-loop-for-coins-doensn’t-work-Java-Soln
  • 내가 계속 헷갈리던게 여기에 정리돼있다.
  • 나는 바깥 for문을 amount로 하고, 안쪽 for문을 coin으로 했는데 그러면 안 된다.
    • 바깥 for문을 amount로 할 때 고려해야할 점들이 더 있다. 다음과 같음..

  class Solution {
      public int change(int amount, int[] coins) {
          int[][] dp = new int[amount+1][coins.length+1];
          for (int i = 0; i<= amount; i++) {
              for (int j = 0; j <= coins.length; j++) {
                  if (i == 0)
                      dp[i][j] = 1;
                  else if (j == 0)
                      dp[i][j] = 0;
                  else {
                      if (coins[j-1] <= i)
                          dp[i][j] = dp[i][j-1] + dp[i - coins[j-1]][j];
                      else
                          dp[i][j] = dp[i][j-1];
                  }
              }
          }
          return dp[amount][coins.length];
      }
  }