题解 | #兑换零钱(一)#

dp[j]表示兑换成j元最少需要多少张纸币，dp[0] = 0。
dp[j] = min( dp[j],dp[j-arr[i]] + 1  )
转移方程表示兑换成j元要么用i-1张货币直接兑换成j元，要么i-1张货币兑换成j-arr[i]元，再加一张价值arr[i]的纸币。
这里的转移方程是对原本二维的dp[i][j]压缩纬度之后的结果，原本dp[i][j]表示用i张货币兑换成j元最少用多少张。
原本对于i的循环还在。因为在i=1的情况下对j进行遍历填充dp表之后，i+1之后dp[j]中保存的是i=1的情况，就是之前的状态，更新最新状态的时候正好需要,所以对dp表进行压缩。
注意边界条件，j要从arr[i]的数值开始，因为用价值arr[i]的货币去兑换小于其本身价值的货币是没有意义的

int min( const int a, const int b )
{
    return a<b?a:b;
}


int minMoney(int* arr, int arrLen, int aim ) 
{
    int dp[aim+1];
    memset( dp,100,sizeof(dp) ); //初始化dp表，初始化dp表后，表内的数据是很大的，并不是100
    dp[0] = 0;
    
    for( int i =0; i < arrLen; ++i )
    {
        for( int j = arr[i]; j <= aim; ++j )
        {
            dp[j] = min( dp[j],dp[j-arr[i]] + 1 );
        }
    }
    
    return dp[aim]>aim?-1:dp[aim];     //初始化dp表的数值是很大的，如果dp表的某个值大于aim表示其根本没有更新，也就是无法兑换
}