R9-dp篇

java">class Solution {public int coinChange(int[] coins, int amount) {int n=coins.length;int [][] f=new int[n+1][amount+1];//除2防止下面+1溢出Arrays.fill(f[0],Integer.MAX_VALUE/2);f[0][0]=0;for (int i=0;i<n;i++){for (int c=0;c<=amount;c++){if(c<coins[i]) f[i+1][c]=f[i][c];else f[i+1][c]=Math.min(f[i][c],f[i+1][c-coins[i]]+1);}}int ret=f[n][amount];return ret<Integer.MAX_VALUE/2?ret:-1;}
}