리트코드 322 코인변경 c++ // 동전dp복습, 리트코드 초기화주의

https://leetcode.com/problems/coin-change/description/

1. 리트코드 초기화주의

리트코드는 아래 함수를 모든tc에 대해 재실행하는듯하다.

따라서 이전 dp값을 그대로 사용해버린다.

-> 함수내에서 초기화 해주면 된다.

int dp[10000+4]; //dp [i][j] : i원을 달성하는 최소 동전갯수, j번째 동전추가시
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // memset(dp,0,sizeof(dp)); //리트코드는 전역변수 재사용하기땜에 초기화해줘야하는듯?!!

 

2. 동전dp복습

1. 최솟값 구하기는 dp를 최대값으로 초기화해야 후에 min()함수를 

쓰기 쉬워진다!!!

2. 1열의 형광색칠한 패딩부분이 핵심이다.

패딩에서 부터 +1 하면서 내코인1개 추가가 구현된다

dp=min(위의값, 내코인1개추가)

 

3. 전체코드

int dp[10000+4]; //dp [i][j] : i원을 달성하는 최소 동전갯수, j번째 동전추가시
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // memset(dp,0,sizeof(dp)); //리트코드는 전역변수 재사용하기땜에 초기화해줘야하는듯?!!
        // if(amount==0) return 0;
        // for(int i=0;i<=amount;++i){
        //     cout<<dp[i]<<" ";
        // }

        // sort(coins.begin(),coins.end());
        // // cout<<coins[0]<<"\n";
        // for(int i=1;i<=amount;++i){
        //     if(i-coins[0]>=0 && i%coins[0]==0){
        //         //cout<<i-coins[j]<<" ";
        //         dp[i]=dp[i-coins[0]]+1;
        //     }
        // }
        // for(int i=0;i<=amount;++i){
        //     cout<<dp[i]<<" ";
        // }

        fill(dp,dp+10004,10004); //최소값 구하기는 최대값으로 초기화!
        dp[0]=0; //0원을 만드는 경우는 0임.

        for(int i=1;i<=amount;++i){
            
            for(int j=0;j<coins.size();++j){
                if(i-coins[j]>=0){
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
                }   
            }

        }   
        
        // for(int i=0;i<=amount;++i){
        //     cout<<dp[i]<<" ";
        // }
        if(dp[amount]==10004) return -1;
        return dp[amount];
    }
};