技术支持 重庆网站,烟台网站建设哪家服务好,洛阳霞光网络科技有限公司,网站制作怎么做网站优化排名最近在做华为机试体验题#xff0c;遇到一个“找零钱”的题目#xff0c;如下
想起之前在牛客网上看到左程云老师讲过的动态规划问题#xff0c;很像#xff0c;题目如下#xff1a; 有数组penny#xff0c;penny中所有的值都为正数且不重复。每个值代表一种面值的货币遇到一个“找零钱”的题目如下
想起之前在牛客网上看到左程云老师讲过的动态规划问题很像题目如下 有数组pennypenny中所有的值都为正数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个整数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?couponAO79vdy
优惠码AO79vdy
