网站的建设包括那几个模块,wordpress 返回首页,大连百度推广排名优化,汽车租赁网站开发学习交流加 个人qq#xff1a; 1126137994个人微信#xff1a; liu1126137994学习交流资源分享qq群#xff1a; 962535112 文章目录1、暴力搜索方法2、记忆搜索方法3、动态规划方法4、各种动态规划方法案例总结#xff1a;给定数组arr#xff0c;arr中所有数都为正数… 学习交流加 个人qq 1126137994个人微信 liu1126137994学习交流资源分享qq群 962535112 文章目录1、暴力搜索方法2、记忆搜索方法3、动态规划方法4、各种动态规划方法案例总结给定数组arrarr中所有数都为正数且不重复每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个正整数aim代表要找的钱数求换钱有多少种方法
这道题可以用暴力搜索记忆搜索动态规划状态继续化简后的动态规划方法等四种方法 在面试中出现类似的题目优化轨迹高度类似
1、暴力搜索方法
下面先看这道题的暴力搜索方法的过程 我们认为使用0张5元让剩下的货币值arr[10,25,1],去组成剩下的钱的过程是一个递归的过程。 同理使用1张5元。2张5元…都会有一个递归的过程
定义一个递归数组int p1(arr,index,aim),它的意思是如果用arr[index…N-1]这些面值的钱组成aim返回总的方法数
public int coins1(int[] arr,int aim)
{if(arrnull||arr.length0||aim0)return 0;return process1(arr,0,aim);
}
public int process1(int[] arr,int index,int aim)
{int res 0;if(indexarr.length)res aim0?1:0;else{for(int i0;arr[index]*iaim;i) //类似于0张5元到200张5元循环组成aimres process1(arr,index1,aim-arr[index]*i);}return res;
}
如果已经使用0张5元和1张10元的情况下后续还需要求p1(arr,2,990)
2:表示剩下钱为arr[2,3]即为arr{25,1}
990:表示要找的剩余的钱数当使用2张5元和0张10元的情况下后续还是要求p1(arr,2,990)
这样的重复计算在暴力搜索中是非常多的这会导致暴力搜索的时间复杂度非常高2、记忆搜索方法
暴力搜索之所以效率低是因为每次计算后都没有把计算所得结果保存起来下次递归后还是要重新计算。
而且我们发现在暴力搜索方法中有以下现象 arr使用不便index和aim始终在变化。可以让p(index,aim)来代替递归过程
还需要新加一个二维数组用于保存每一次递归的结果 代码如下
public int coins2(int[] arr,int aim)
{if(arrnull||arr.length0||aim0)return 0;int[][] map new int[arr.length][aim1];return process2(arr,0,aim,map);
}
public int process2(int[] arr,int index,int aim,int[][] map)
{int res 0;if(indexarr.length)res aim0?1:0;else{int mapValue 0;for(int i0;arr[index]*iaim;i) //类似于0张5元到200张5元循环组成aim{mapValue map[index1][aim-arr[index]*i];if(mapValue!0)res mapValue-1?0:mapValue;elseres process2(arr,index1,aim-arr[index]*i,map);}}map[index][aim]res0?-1:res;return res;
}3、动态规划方法 如上图所示dp[i][j] 表示使用arr[0…i] 货币的情况下组成钱数j有多少种方法。上图第一列为1代表钱数为0每一种货币都可以组成00乘以任意面值的货币。 需要一行一行的计算从上到下从左到右从子问题到整个问题最终最右下角的值也就是dp[N-1][aim]就是我们要求的值
要求dp[i][j],需要枚举它上一行左边的所有值dp[i-1][1~j]
记忆搜索与动态规划的联系
那么什么是动态规划呢
动态规划方法的转化过程
动态规划过程的关键点
面试题 有数组pennypenny中所有的值都为正数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个整数aim(小于等于1000)代表要找的钱数求换钱有多少种方法。
给定数组penny及它的大小(小于等于50)同时给定一个整数aim请返回有多少种方法可以凑成aim。
测试样例 [1,2,4],3,3 返回2
class Exchange {
public:int countWays(vectorint penny, int n, int aim) {// write code hereint dp[n][aim1];//矩阵初始化for(int i0;in;i){for(int j0;jaim1;j){dp[i][j]0;}}//初始化第一行数值for(int j0;jaim1;j){if(j%penny[0]0)dp[0][j]1;}//初始化第一列数值for(int i0;in;i){dp[i][0]1;}//求其他行数值for(int i1;in;i){for(int j1;jaim1;j){ for(int k0;(j-k*penny[i])0;k) {//根据上面分析的公式dp[i][j] dp[i-1][j-k*penny[i]];} }}return dp[n-1][aim];}
};4、各种动态规划方法案例总结
我们上述所讲的动态规划方法其实是还可以经过优化的
下面先来卡一个例子 案例1 给定一个矩阵m从左上角开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和返回所有的路径中最小的路径和如果给定的路径如下图则最小的路径和应该为1,3,1,0,6,1,0这条路径返回最小值为12
假设矩阵m的大小为M*N,行数为M列数为N生成大小和m一样的矩阵dp行数为M列数为Ndp[i][j]的值等于从左上角也就是0,0 走到ij位置的最小路径和。
那么除了第一行和第一列的值其他部分的值为只能是从上面过来或者从左边过来
那么我们就可以先从左到右先计算每一行的值然后从上到下计算每一列的值最后最右下角的值就是我们要返回的值了
案例2
动态规划的思路如下
案例3 则我们可以选择上述三种情况下最大的值作为返回值。
案例4 解决方法
案例5
那么矩阵最右下角的值就是我们需要返回的值
下一篇文章将针对上述几个案例的具体算法题进行编程验证
