当前位置: 首页> 娱乐> 八卦 > 【16】暴力递归改dp(上)

【16】暴力递归改dp(上)

时间:2025/7/10 18:17:34来源:https://blog.csdn.net/2201_75414908/article/details/141292349 浏览次数:0次

目录

一.机器人问题

二.最少硬币问题


一.机器人问题

题目:N表示位置1-N,S表示机器人开始位置,e表示结尾位置,k表示机器人必须走k步,问一共有多少种方法?

情况:

  • 如果第1个位置,下次只能向第2个位置走
  • 如果第N个位置,下次只能向N-1个位置走
  • 若一般位置cur,下次可以向cur-1和cur+1位置走

暴力递归版本: 

	public static int ways1(int N, int M, int K, int P) {// 参数无效直接返回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步要走// 走向右之后,后续的过程就是,来到cur+1位置上,还剩rest-1步要走// 走向左、走向右是截然不同的方法,所以总方法数要都算上return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);}

暴力递归不好:f(2, 2)展开算过一次,下一次f(2,2)还是展开计算,所以存在很多重复解。 

记忆化版本:

public static int ways1(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];for(int i=0;i<=K;i++) {for(int j=0;j<=N;j++) {dp[i][j]=-1;}}// 总共N个位置,从M点出发,还剩K步,返回最终能达到P的方法数return walk(N, M, K, P, dp);}public static int walk(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;}else if (cur == 1) {dp[rest][cur]=walk(N, 2, rest - 1, P, dp);}else if (cur == N) {dp[rest][cur]=walk(N, N - 1, rest - 1, P, dp);}else {dp[rest][cur]=walk(N, cur + 1, rest - 1, P, dp) + walk(N, cur - 1, rest - 1, P, dp);}return dp[rest][cur];}

动态规划版本:

边界条件 <=>  初始化条件

递归改动态规划 <=> 翻译出依赖关系

	public static int ways2(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];}

二.最少硬币问题

题目:给出N枚硬币,可以能存在重复面值硬币,每枚硬币只能使用一次,求组合出aim数值的所需的最少硬币数。

从左到右逐个硬币考虑,当发现方法一定不可行,直接返回-1

暴力递归版本:

	public static int minConins1(int[] arr, int aim) {return process(arr, 0, aim);}public static int process(int[] arr, int index, int rest) {if(rest<0) {return -1;}if(rest==0) {return 0;}// rest > 0if(index==arr.length) {return -1;}// rest > 0 并且还有硬币int p1 = process(arr, index+1, rest);int p2Next = process(arr, index+1, rest-arr[index]);if(p1==-1&&p2Next==-1) {return -1;}else {if(p1==-1) {return p2Next+1;}else if(p2Next==-1) {return p1;}else return Math.min(p1, p2Next+1);}}

 记忆化版本:

	public static int minConins2(int[] arr, int aim) {int[][] dp=new int[arr.length+1][aim+1];for(int i=0;i<=arr.length;i++) {for(int j=0;j<=aim;j++) {dp[i][j]=-2;}}return process(arr, 0, aim, dp);}public static int process(int[] arr, int index, int rest, int[][] dp) {if(rest<0) {return -1;}if(dp[index][rest] != -2) {return dp[index][rest];}if(rest==0) {dp[index][rest] = 0;}else if(index==arr.length) {dp[index][rest] = -1;}else {// rest > 0 并且还有硬币int p1 = process(arr, index+1, rest, dp);int p2Next = process(arr, index+1, rest-arr[index], dp);if(p1==-1&&p2Next==-1) {dp[index][rest] = -1;}else {if(p1==-1) {dp[index][rest] = p2Next+1;}else if(p2Next==-1) {dp[index][rest] = p1;}else dp[index][rest] = Math.min(p1, p2Next+1);}}return dp[index][rest];}

动态规划版本:

	public static int minCoins3(int[] arr, int aim) {int[][] dp=new int[arr.length+1][aim+1];for(int i=0;i<=arr.length;i++) {dp[i][0]=0;}for(int i=0;i<=aim;i++) {dp[arr.length][rest] = -1;}for(int index = N-1;index >= 0 ;index--) {for(int rest=1;rest<=aim;rest++) {int p1=dp[index+1][rest];int p2Next=-1;if(rest-arr[index] >= 0) {p2Next = dp[index+1][rest-arr[index]];}if(p1==-1&&p2Next==-1) {dp[index][rest]=-1;}else {if(p1==-1) {dp[index][rest] = p1;}else if(p2Next==-1) {dp[index][rest] = p2Next+1;}else dp[index][rest] = Math.min(p1, p2Next+1);}}}return dp[0][aim];}

关键字:【16】暴力递归改dp(上)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: