动态规划c++

动态规划的基本概念及思想

打家劫舍http://t.csdnimg.cn/TQm9G

零钱兑换：

问题描述：
有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。

思路分析：
? ?设dp[i][j]代表钱为j，i纸币的面值时共有的找钱方法。先找到每种面值的解决方法，然后递推，逐步再求出所有面值都有的时候的找钱方法。
? ?如果钱j为0，那么方法肯定为0。如果钱数是第一种纸币的面值的整数倍，那么只有1种方法，或者0种方法，这是初始条件。
? ?之后对钱和面值开始遍历，如果钱数大于面值（证明可以找零钱），那么方法数= 面值是前边一种，钱数不变的的时候的方法 ?+ ? 面值不变，钱数=钱数-面值 时的方法（dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]）。因为，对于某种面值我们有两种情况，用或不用，不用就是dp[i - 1][j] ?，用了，那么此时的钱就必须先减取面值，j-penny[i]，所以是dp[i][j - penny[i]]。至于考虑用的张数，这个会在遍历钱j的时候考虑到。
代码：

int countWays(int penny[], int n, int aim) {
              //penny 面值数组， 面值个数，aim 总钱数
 	int dp[n][aim+1];
	//初始状态
	for (int i = 0; i < n; i++) dp[i][0] = 1;//aim=0时
	for (int j = 1; j <= aim; j++) {//第一行
		int i = penny[0];
		if (j%i == 0)
			dp[0][j] = 1;
		else dp[0][j] = 0;
 
	}
	//从上到下 从左到右
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= aim; j++) {
			if (j >= penny[i]) {//在前i-1项里面拼凑j，和在前i项里拼凑j-penny[i]--默认已经选择一个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];
}