最近在做華為機試體驗題，遇到一個“找零錢”的題目，如下
想起之前在牛客網上看到左程云老師講過的動態規劃問題，很像，題目如下：
有數組penny，penny中所有的值都為正數且不重復。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數aim(小于等于1000)代表要找的錢數，求換錢有多少種方法。
給定數組penny及它的大小(小于等于50)，同時給定一個整數aim，請返回有多少種方法可以湊成aim。
用Java編程實現：
public class DynamicProgramming {public int countWays(int[] penny, int n, int aim) {int[][] dp = new int[n][aim + 1];// 定義一個矩陣，dp[i][j]表示用penny[0...i-1]個貨幣組成j的錢數if (penny.length == 0 || aim < 0)return 0;for (int i = 0; i < n; i++) {dp[i][0] = 1;// 第一列全是1}for (int i = 0; i < aim + 1; i++)dp[0][i] = (i % penny[0] == 0) ? 1 : 0;// 第一行中是i的倍數的則為1for (int i = 1; i < n; i++) {for (int j = 1; j < aim + 1; j++) {if (j >= penny[i]) {dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]];} else {dp[i][j] = dp[i - 1][j];}}}return dp[n - 1][aim];}//以下是自己添加的測試用例，在牛客網上不需要輸入（它自帶測試用例）public static void main(String[] args) {int[] penny = { 1, 3, 4 };int n = penny.length;int aim = 3;DynamicProgramming dynamicProgramming = new DynamicProgramming();System.out.println(dynamicProgramming.countWays(penny, n, aim));}
}
輸出：3
關于動態規劃，啰嗦一句，先看懂暴力搜索，動態規劃就不難理解。
課程參考地址：http://www.nowcoder.com/courses/1?coupon=AO79vdy ?
優惠碼：AO79vdy
