【16】暴力递归改dp（上）

目录

一.机器人问题

二.最少硬币问题

---

一.机器人问题

题目：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];}