网站建设程序策划书,美食网站主页怎么做,十堰推广公司,wordpress 什么值得买主题 最新v目录
动态规划的详解
动态规划的应用 机器人到达指定位置数 换钱的最少货币数 排成一条线的纸牌博弈问题 象棋中马的跳法 Bob的生存概率 换钱的方法数
动态规划的总结
动态规划的详解 暴力尝试递归操作中有很多重复计算的操作#xff0c;浪费时间。动态规划就是减少暴力…目录
动态规划的详解
动态规划的应用 机器人到达指定位置数 换钱的最少货币数 排成一条线的纸牌博弈问题 象棋中马的跳法 Bob的生存概率 换钱的方法数
动态规划的总结
动态规划的详解 暴力尝试递归操作中有很多重复计算的操作浪费时间。动态规划就是减少暴力尝试中重复计算的技巧这种技巧就是一个大型套路先写出用尝试的思路解决问题的递归函数而不用操心时间复杂度这个过程是无可替代的没有套路的只能依靠个人智慧或者足够多的经验。 但是怎么把尝试的版本优化成动态规划是有固定套路的大体步骤如下 (1)找到什么可变参数可以代表一个递归状态也就是哪些参数一旦确定返回值就确定了 (2)把可变参数的所有组合映射成一张表有 1 个可变参数就是一维表2 个可变参数就是二维表...... (3)最终答案要的是表中的哪个位置在表中标出 (4)根据递归过程的 base case把这张表的最简单、不需要依赖其他位置的那些位置填好值 (5)根据递归过程非base case的部分也就是分析表中的普遍位置需要怎么计算得到那么这张表的填写顺序也就确定了 (6)填好表返回最终答案在表中位置的值 对于代码方面的修改也是有固定套路的对于记忆化搜索的方法就是首先写出尝试的思路解决问题的递归函数然后在此基础上先改成记忆化搜索的程序也就是添加上数组记录计算过的值避免出现重复计算的过程后面执行程序时对于计算过的直接使用不再重复计算。 严格位置表依赖的方法是将按照上面的步骤将目标值和初始确定的值在程序中先确定出来然后对递归程序进行适当更改即可完成。
动态规划的应用 机器人到达指定位置数 【题目】 假设有排成一行的N个位置记为1~NN 一定大于或等于 2。开始时机器人在其中的 M 位置上(M一定是 1~N 中的一个)机器人可以往左走或者往右走如果机器人来到1位置那么下一步只能往右来到2 位置;如果机器人来到N位置那么下一步只能往左来到 N-1 位置。规定机器人必须走K步最终能来到P位置(P 也一定是 1~N 中的一个)的方法有多少种。给定四个参数 N、M、K、P返回方法数。 【举例】 N5,M2,K3,P3 上面的参数代表所有位置为1 2 3 4 5。机器人最开始在2位置上必须经过3步最后到达3位置。走的方法只有如下3种: 1)从2到1从1到2从2到3 2)从2到3从3到2从2到3 3)从2到3从3到4从4到3。所以返回方法数3。 N3,M1,K3,P3 上面的参数代表所有位置为1 2 3。机器人最开始在1位置上必须经过3步最后到达3位置。怎么走也不可能所以返回方法数0。 public static int ways1(int N, int M, int K, int P) {//使用暴力递归的方式解决问题,时间复杂度能达到O2^k)// 参数无效直接返回0if (N 2 || K 1 || M 1 || M N || P 1 || P N) {return 0;}// 总共N个位置从M点出发还剩K步返回最终能达到P的方法数return walk(N, M, K, P);}// N : 位置为1 ~ N固定参数// cur : 当前在cur位置可变参数// rest : 还剩res步没有走可变参数// P : 最终目标位置是P固定参数// 该函数的含义只能在1~N这些位置上移动当前在cur位置走完rest步之后停在P位置的方法数作为返回值返回public static int walk(int N, int cur, int rest, int P) {// 如果没有剩余步数了当前的cur位置就是最后的位置// 如果最后的位置停在P上那么之前做的移动是有效的// 如果最后的位置没在P上那么之前做的移动是无效的if (rest 0) {return cur P ? 1 : 0;}// 如果还有rest步要走而当前的cur位置在1位置上那么当前这步只能从1走向2// 后续的过程就是来到2位置上还剩rest-1步要走if (cur 1) {return walk(N, 2, rest - 1, P);}// 如果还有rest步要走而当前的cur位置在N位置上那么当前这步只能从N走向N-1// 后续的过程就是来到N-1位置上还剩rest-1步要走if (cur N) {return walk(N, N - 1, rest - 1, P);}// 如果还有rest步要走而当前的cur位置在中间位置上那么当前这步可以走向左也可以走向右// 走向左之后后续的过程就是来到cur-1位置上还剩rest-1步要走// 走向右之后后续的过程就是来到cur1位置上还剩rest-1步要走// 走向左、走向右是截然不同的方法所以总方法数要都算上return walk(N, cur 1, rest - 1, P) walk(N, cur - 1, rest - 1, P);}public static int ways2(int N, int M, int K, int P) {//使用记忆化搜索的方式解决问题时间复杂度为O(M*K)// 参数无效直接返回0if (N 2 || K 1 || M 1 || M N || P 1 || P N) {return 0;}int[][] dp new int[K 1][N 1];//定义一个数组存放计算过的内容,作为缓存结构for(int i0;ik;i){for(int j0;jN;j){dp[i][j] -1;}}// 总共N个位置从M点出发还剩K步返回最终能达到P的方法数return walk2(N, M, K, P , dp);}// N : 位置为1 ~ N固定参数// cur : 当前在cur位置可变参数// rest : 还剩res步没有走可变参数// P : 最终目标位置是P固定参数// 该函数的含义只能在1~N这些位置上移动当前在cur位置走完rest步之后停在P位置的方法数作为返回值返回public static int walk2(int N, int cur, int rest, int P,int[][] dp) {if(dp[rest][cur]!-1){//如果某个值已经计算过不需要再重复计算直接返回return dp[rest][cur];}//还没有计算过,每次返回之前把答案记录下来if (rest 0) {dp[rest][cur] cur P ? 1 : 0;return dp[rest][cur];}// 如果还有rest步要走而当前的cur位置在1位置上那么当前这步只能从1走向2// 后续的过程就是来到2位置上还剩rest-1步要走if (cur 1) {dp[rest][cur] walk2(N, 2, rest - 1, P);}// 如果还有rest步要走而当前的cur位置在N位置上那么当前这步只能从N走向N-1// 后续的过程就是来到N-1位置上还剩rest-1步要走else if (cur N) {dp[rest][cur] walk2(N, N - 1, rest - 1, P);}else{dp[rest][cur] walk2(N, cur 1, rest - 1, P) walk2(N, cur - 1, rest - 1, P);}return dp[rest][cur];}public static int ways3(int N, int M, int K, int P) {//严格位置表依赖的方式// 参数无效直接返回0if (N 2 || K 1 || M 1 || M N || P 1 || P N) {return 0;}int[][] dp new int[K 1][N 1];//定义一个数组存放计算过的内容dp[0][P] 1;//终点的位置在格子中标出来for (int i 1; i K; i) {//然后从第一行第一列开始下面的过程根据递归的依赖性进行改编for (int j 1; j N; j) {if (j 1) {dp[i][j] dp[i - 1][2];} else if (j N) {dp[i][j] dp[i - 1][N - 1];} else {dp[i][j] dp[i - 1][j - 1] dp[i - 1][j 1];}}}return dp[K][M];} 换钱的最少货币数 【题目】给定数组 arrarr中所有的值都为正数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个整数 aim代表要找的钱数求组成aim的最少货币数。 【举例】arr[5,2,3]aim20。4 张 5 元可以组成 20 元其他的找钱方案都要使用更多张的货币所以返回 4。arr[5,2,3]aim0。不用任何货币就可以组成0元返回 0。arr[3,5]aim2。根本无法组成2元钱不能找开的情况下默认返回-1。 public static int minCoins1(int[] arr, int aim) {//暴力递归方式求解if (arr null || arr.length 0 || aim 0) {return -1;}return process(arr, 0, aim);}// 当前考虑的面值是arr[i]还剩rest的钱需要找零// 如果返回-1说明自由使用arr[i..N-1]面值的情况下无论如何也无法找零rest// 如果返回不是-1代表自由使用arr[i..N-1]面值的情况下找零rest需要的最少张数public static int process(int[] arr, int i, int rest) {if(rest 0){return -1;}if(rest 0){return 0;}//rest0但是没有钱if(i arr.length){return -1;}//rest 0并且也有硬币,有两种选择int p1 process(arr,i1,rest);//表示不要下一个硬币int p2Next process(arr,i1,rest-arr[i]);//表示要下一个硬币if(p1 -1p2Next -1){return -1;}else{if(p1 -1){return p2Next 1;//加1是因为p2Next表示要下一个硬币}if(p2 -1){return p1;}return Math.min(p1,p2Next1);}}public static int minCoins2(int[] arr, int aim) {//记忆化搜索的动态规划的方式求解if (arr null || arr.length 0 || aim 0) {return -1;}int[][] dp new int[arr.length1][aim1];//建立数组记录计算的过程for(int i 0;i arr.length; i){//初始化for(int j 0;j aim; j){dp[i][j] -2;}}return process2(arr, 0, aim,dp);}// 当前考虑的面值是arr[i]还剩rest的钱需要找零// 如果返回-1说明自由使用arr[i..N-1]面值的情况下无论如何也无法找零rest// 如果返回不是-1代表自由使用arr[i..N-1]面值的情况下找零rest需要的最少张数public static int process2(int[] arr, int i, int rest , int[][] dp) {if(rest 0){return -1;}if(dp[i][rest]!-2){//如果已经计算过直接返回return dp[i][rest];}if(rest 0){dp[i][rest] 0}else if(i arr.length){dp[i][rest] -1;}else{//rest 0并且也有硬币,有两种选择int p1 process2(arr,i1,rest,dp);//表示不要下一个硬币int p2Next process2(arr,i1,rest-arr[i],dp);//表示要下一个硬币if(p1 -1p2Next -1){dp[i][rest] -1;}else{if(p1 -1){dp[i][rest] p2Next 1;//加1是因为p2Next表示要下一个硬币}else if(p2 -1){dp[i][rest] p1;}else{dp[i][rest] Math.min(p1,p2Next1);}}}return dp[i][rest];}public static int minCoins3(int[] arr, int aim) {//严格表结构的动态规划方式求解if (arr null || arr.length 0 || aim 0) {return -1;}int N arr.length;int[][] dp new int[N 1][aim 1];// 设置最后一排的值除了dp[N][0]为0之外其他都是-1//一些知道的初始位置设置好for (int col 1; col aim; col) {dp[N][col] -1;}for(int row 0;row N;row){dp[row][0] 0;}//把递归的过程放过来然后根据表结构进行适当的改动for(int i N-1; i 0;i--){for(int rest 1;rest aim;rest){int p1 dp[i1][rest];int p2Next -1;if(rest - arr[i] 0){p2Next dp[i1][rest - arr[i]];}if(p1 -1p2Next -1){dp[i1][rest] -1;}else{if(p1 -1){dp[i1][rest] p2Next 1;//加1是因为p2Next表示要下一个硬币}if(p2 -1){dp[i1][rest] p1;}dp[i1][rest] Math.min(p1,p2Next1);}}}return dp[0][aim];}排成一条线的纸牌博弈问题 【题目】给定一个整型数组 arr代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌规定玩家A先拿玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩 家B都绝顶聪明。请返回最后获胜者的分数。 【举例】arr[1,2,100,4]。开始时玩家A只能拿走1或4。如果玩家A拿走1则排列变为[2,100,4]接下来玩家B可以拿走2或4然后继续轮到玩家A。如果开始时玩家A拿走4则排列变为[1,2,100]接下来玩家B可以拿走1或100然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4因为拿4之后玩家B将拿走100。所以玩家A会先拿1让排列变为[2,100,4]接下来玩家B 不管怎么选100都会被玩家A拿走。玩家A会获胜分数为101。所以返回101。arr[1,100,2]。 开始时玩家A不管拿1还是2玩家B作为绝顶聪明的人都会把100拿走。玩家B会获胜分数为 100。所以返回100。 public static int win1(int[] arr) {//暴力递归的方式求解if (arr null || arr.length 0) {return 0;}return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));//先手和后手谁的分数多谁获胜}public static int f(int[] arr, int i, int j) {//先手函数if (i j) {//如果只有一个数字先手直接拿了return arr[i];}return Math.max(arr[i] s(arr, i 1, j), arr[j] s(arr, i, j - 1));//如果不是只有一个数字那么先手选择拿左边和右边两种情况下最大的那一种情况}public static int s(int[] arr, int i, int j) {//后手函数if (i j) {//如果只有一张牌后手拿不到return 0;}return Math.min(f(arr, i 1, j), f(arr, i, j - 1));//如果不只有一张牌后手只能拿到剩下情况下最小的那种情况}//在范围上尝试的模型行是不可能超过列的左下角区域都是不存在的先填对角线//动态规划一定要画图操作用最基础的递归操作进行画图找到格子之间的关系然后递归的过程进行改写public static int win2(int[] arr) {if (arr null || arr.length 0) {return 0;}//建立两个格子int[][] f new int[arr.length][arr.length];int[][] s new int[arr.length][arr.length];for (int j 0; j arr.length; j) {f[j][j] arr[j];//对角线元素填上s[j][j] 0;for (int i j - 1; i 0; i--) {//只对右上角进行操作两个表互相依赖f[i][j] Math.max(arr[i] s[i 1][j], arr[j] s[i][j - 1]);s[i][j] Math.min(f[i 1][j], f[i][j - 1]);}}return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);} 象棋中马的跳法 【题目】请同学们自行搜索或者想象一个象棋的棋盘然后把整个棋盘放入第一象限棋盘的最左下角是(0,0)位置。那么整个棋盘就是横坐标上9条线、纵坐标上10条线的一个区域。给你三个 参数xyk返回如果“马”从(0,0)位置出发必须走k步最后落在(x,y)上的方法数有多少种 public static int getWays(int x, int y, int step) {//暴力递归的方式求解return process(x, y, step);}public static int process(int x, int y, int step) {if (x 0 || x 8 || y 0 || y 9) {return 0;}//x,y位置越界0种方法无法到达if (step 0) {//不能再动了return (x 0 y 0) ? 1 : 0;//一开始在00位置如果想要到达的就是00位置那么已经到达一种方法如果不是那么无法到达}//不越界也可以跳把跳一步可以跳到(x,y)位置的情况都写出来return process(x - 1, y 2, step - 1) process(x 1, y 2, step - 1) process(x 2, y 1, step - 1) process(x 2, y - 1, step - 1) process(x 1, y - 2, step - 1) process(x - 1, y - 2, step - 1) process(x - 2, y - 1, step - 1) process(x - 2, y 1, step - 1);}public static int dpWays(int x, int y, int step) {//严格表结构的动态规划方式求解//有三个可变参数那么建立一个三维立体其它的按照递归的程序和立体图形各个之间的关系进行改写if (x 0 || x 8 || y 0 || y 9 || step 0) {return 0;}//这个立体之外的部分都是0int[][][] dp new int[9][10][step 1];//建立一个立体dp[0][0][0] 1;//第0层的面只有00位置是1其它都是0for (int h 1; h step; h) {//每一层处理每一层只依赖于下一层的内容for (int r 0; r 9; r) {for (int c 0; c 10; c) {dp[r][c][h] getValue(dp, r - 1, c 2, h - 1);dp[r][c][h] getValue(dp, r 1, c 2, h - 1);dp[r][c][h] getValue(dp, r 2, c 1, h - 1);dp[r][c][h] getValue(dp, r 2, c - 1, h - 1);dp[r][c][h] getValue(dp, r 1, c - 2, h - 1);dp[r][c][h] getValue(dp, r - 1, c - 2, h - 1);dp[r][c][h] getValue(dp, r - 2, c - 1, h - 1);dp[r][c][h] getValue(dp, r - 2, c 1, h - 1);}}}return dp[x][y][step];}public static int getValue(int[][][] dp, int row, int col, int step) {//防止越界的函数如果越界取0如果没有越界拿到相应位置的值if (row 0 || row 8 || col 0 || col 9) {return 0;}return dp[row][col][step];}Bob的生存概率 【题目】给定五个参数n,m,i,j,k。表示在一个N*M的区域Bob处在(i,j)点每次Bob等概率的向上、下、左、右四个方向移动一步Bob必须走K步。如果走完之后Bob还停留在这个区域上 就算Bob存活否则就算Bob死亡。请求解Bob的生存概率返回字符串表示分数的方式。 public static String bob1(int N, int M, int i, int j, int K) {//暴力递归的方式求解long all (long) Math.pow(4, K);//总的方法数位4的k次方因为每一个位置的选择有4种一共走k步long live process(N, M, i, j, K);long gcd gcd(all, live);//概率就是活下来的除以总的return String.valueOf((live / gcd) / (all / gcd));}public static long process(int N, int M, int row, int col, int rest) {if (row 0 || row N || col 0 || col M) {return 0;}//如果越界死亡if (rest 0) {//如果已经走完也没有越界活下来return 1;}//Bob总体活下来的方法数等于他往上往下往左往右分别走一步且活下来的方法数long live process(N, M, row - 1, col, rest - 1);live process(N, M, row 1, col, rest - 1);live process(N, M, row, col - 1, rest - 1);live process(N, M, row, col 1, rest - 1);return live;}public static long gcd(long m, long n) {//求最大公约数return n 0 ? m : gcd(n, m % n);}public static String bob2(int N, int M, int i, int j, int K) {//严格表结构的动态规划的方式同样的按照递归的方式分析立体结构的关系求解int[][][] dp new int[N 2][M 2][K 1];//建立一个立体for (int row 1; row N; row) {for (int col 1; col M; col) {dp[row][col][0] 1;}}for (int rest 1; rest K; rest) {for (int row 1; row N; row) {for (int col 1; col M; col) {dp[row][col][rest] dp[row - 1][col][rest - 1];dp[row][col][rest] dp[row 1][col][rest - 1];dp[row][col][rest] dp[row][col - 1][rest - 1];dp[row][col][rest] dp[row][col 1][rest - 1];}}}long all (long) Math.pow(4, K);long live dp[i 1][j 1][K];long gcd gcd(all, live);return String.valueOf((live / gcd) / (all / gcd));} 换钱的方法数 有给定面值的零钱数在arr数组中最终需要找零的钱数为aim返回最终能够找零的方法数。
public static int way1(int[] arr, int aim){//暴力递归方法的求解return process(arr,0,aim);//可以使用arr[0..]中的所有面值
}
//可以自由使用arr[index..]所有的面值
pubilc static int process(int[] arr,int index,int rest){if(index arr.length){//如果已经没有钱数可以选择return rest 0? 1:0;//那么如果不需要货币只有一种方法其它的返回0}int ways 0;for(int zhang 0; arr[index] * zhang rest; zhang ){//只要选择的面值乘以张数不超过总计需要的就可以随便选ways process(arr,index 1,rest - arr[index] * zhang);}return ways;
}
public static int ways2(int[] arr,int aim){//严格表结构的动态规划的方式求解没有优化枚举结构还是对递归方式进行适当的改动即可if(arr null||arr.length 0){return 0;}int N arr.length;int[][] dp new int[N1][aim1];dp[N][0] 1;for(int index N-1;index 0;index--){for(int rest 0;rest aim;rest){int ways 0;for(int zhang 0;arr[index] * zhang rest;zhang ){ways dp[index1][rest - arr[index] * zhang];}dp[index][rest] ways;}}return dp[0][aim];
}
public static int ways3(int[] arr,int aim){//严格表结构的动态规划的方式求解优化枚举结构其实也就是通过对格子中位置求解的观察发现枚举行为和周围格子的关系利用这个关系减少优化称为斜率优化对于同一行重复需要的内容不再重新计算if(arr null||arr.length 0){return 0;}int N arr.length;int[][] dp new int[N1][aim1];dp[N][0] 1;for(int index N-1;index 0;index--){for(int rest 0;rest aim;rest){dp[index][rest] dp[index][rest];//一个新的需要计算的格子一定需要它下面的格子。if(rest - arr[index] 0){//如果还没有凑够dp[index][rest] dp[index][rest - arr[index]];//加上自己同行减去本行的面值位置的值}}}return dp[0][aim];
}
动态规划的总结 动态规划首先最重要的就是尝试尝试的方式有从左到右以及范围尝试等比较重要的尝试方法然后根据对题目的分析写出暴力递归方式的代码此时加上一个缓存数组减少重复内容的重复计算也就是改写成记忆化搜索的动态规划方式此时并没有研究各个变量之间的依赖性只是加了一个缓存结构。后面再根据这些关系画出严格表结构根据一些知道的内容对表架构进行填充表中需要求解的位置根据记忆化搜索的代码和暴力递归的代码分析出各个格子之间的关系此时就可以根据暴力递归的代码该写出严格表结构的动态规划的代码写出严格表结构进行分析能够对类似于枚举行为的结构进行优化这是非常重要的。 而尝试方法的好坏考虑的有两个方面一是可变参数的个数可变参数的个数越少分析严格表结构时维度越低更简单。二是单可变参数的维度也就是一个参数的维度最好就是一个整数这个是一定要保证的。
