算法基础提升学习3 算法基础提升学习3

暴力递归转动态规划题机器人到达指定位置
假设有排成一行的 N 个位置，记为 1~N，N 一定大于或等于 2。开始时机器人在其中的 M 位置上(M 一定是 1~N 中的一个)，机器人可以往左走或者往右走，如果机器人来到 1 位置，那么下一步只能往右来到 2 位置; 如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。规定机器人必须走 K 步，最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。给定四个参数 N、M、K、P，返回方法数。
转换为动态规划的思路

想出暴力递归的方法
根据暴力递归中变量的数量，设计表，表的范围参考变量的范围
在第二部的基础上，寻找规律，比如那些列，那些行一开始就是可以确定的，然后找出正确方向顺序来遍历刚才第二部设计的表，将基本位置补全。

/** * @Author: 郜宇博 * @Date: 2021/11/12 14:41 */ public class RobotCounts { public static void main(String[] args) { long s1 = System.currentTimeMillis(); //System.out.println(getRobotCounts1(7, 3, 30, 5)); long s2 = System.currentTimeMillis(); System.out.println(getRobotCounts2(7,3,5000,5)); long s3 = System.currentTimeMillis(); System.out.println(fuc3(7,3,1000000,5)); long s4 = System.currentTimeMillis(); System.out.println("s1="+(s2-s1)); System.out.println("s2="+(s3-s2)); System.out.println("s3="+(s4-s3)); } //开始在M位置,走K步，最后到P，一共有1-N个位置 public static int getRobotCounts1(int N,int M,int K,int P){ return fuc(N,M,K,P); } public static int getRobotCounts2(int N,int M,int K,int P){ //使用表存储 int [][]dp = new int[N+1][K+1]; //初始化表,初始化时看可变参数的变化范围 for (int i = 0; i < N+1; i++) { for(int j = 0; j < K+1; j++){ dp[i][j] = -1; } } return fuc1(N,M,K,P,dp); } public static int getRobotCounts3(int N,int M,int K,int P){ //使用表存储 int [][]dp = new int[N+1][K+1]; //初始化表,初始化时看可变参数的变化范围 for (int i = 0; i < N+1; i++) { for(int j = 0; j < K+1; j++){ dp[i][j] = -1; } } return fuc1(N,M,K,P,dp); } /** * 方法一：暴力递归 * @param N 一共有1-N个位置 * @param cur 当前位置 M * @param rest 剩余步 K * @param P 目标点 * @return 当前情况下到P的可能数 */ public static int fuc(int N,int cur,int rest,int P){ //base case if (rest == 0){ //没步数，看是否到终点 return cur == P? 1:0; } //到两边了 if (cur == 1){ return fuc(N,2,rest-1,P); } if (cur == N){ return fuc(N,N-1,rest-1,P); } //在中间 return fuc(N,cur-1,rest-1,P) + fuc(N,cur+1,rest-1,P); } /** * 方法二：记忆存储 * @param N 一共有1-N个位置 * @param cur 当前位置 * @param rest 剩余步 * @param P 目标点 * @return 当前情况下到P的可能数 */ public static int fuc1(int N,int cur,int rest,int P,int[][]dp){ if (dp[cur][rest] != -1){ return dp[cur][rest]; } if (rest == 0){ dp[cur][rest]= cur == P? 1:0; return dp[cur][rest]; } else { if (cur == 1){ dp[cur][rest]= fuc1(N,2,rest-1,P,dp); } else if (cur == N){ dp[cur][rest]= fuc1(N,N-1,rest-1,P,dp); } else { dp[cur][rest]=fuc1(N,cur-1,rest-1,P,dp) + fuc1(N,cur+1,rest-1,P,dp); } }return dp[cur][rest]; } /** * 方法三：动态规划 * @param N 一共有1-N个位置 * @param M 当前位置 * @param K 剩余步 * @param P 目标点 * @return 当前情况下到P的可能数 * dp[剩余步数][当前位置] */ public static int fuc3(int N,int M,int K,int P){ 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][j+1]; } else if (j == N){ dp[i][j] = dp[i-1][j-1]; } //中间 else { dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; }} } return dp[K][M]; }}

棋盘问题
马从0，0位置出发到x,y，只能走step步，有多少种可能
相当于从x,y出发到0，0

/** * @Author: 郜宇博 * @Date: 2021/11/12 17:56 */ public class HorseCounts { public static void main(String[] args) { long s1 = System.currentTimeMillis(); System.out.println(getHorseCounts1(7, 7, 8)); long s2 = System.currentTimeMillis(); System.out.println(getHorseCounts2(7, 7, 15)); long s3 = System.currentTimeMillis(); System.out.println("S1="+(s2-s1)); System.out.println("S2="+(s3-s2)); } public static int getHorseCounts1(int x,int y, int step){ return f1(x,y,step); } public static int getHorseCounts2(int x,int y, int step){ if (x < 0 || x > 8 || y < 0 || y > 9){ return 0; } //存储的为x,y到0，0可以走step不得所有可能数 int[][][] dp = new int[9][10][step+1]; dp[0][0][0] = 1; for (int k = 1; k <= step; k++){ for (int i = 0; i < 9; i++){ for (int j = 0; j < 10; j++){ //只和上一层有关，第0层初始状态，第一层能由第0层推出。。。。 dp[i][j][k] += getValue(dp,i-1,j-2,k-1); dp[i][j][k] += getValue(dp,i-2,j-1,k-1); dp[i][j][k] += getValue(dp,i-2,j+1,k-1); dp[i][j][k] += getValue(dp,i-1,j+2,k-1); dp[i][j][k] += getValue(dp,i+1,j+2,k-1); dp[i][j][k] += getValue(dp,i+2,j+1,k-1); dp[i][j][k] += getValue(dp,i+2,j-1,k-1); dp[i][j][k] += getValue(dp,i+1,j-2,k-1); } } } return dp[x][y][step]; }private static int getValue(int[][][] dp, int x, int y, int step) { if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0){ return 0; } return dp[x][y][step]; }/** * 从x,y出发，到0，0点的可能数 */ private static int f1(int x, int y, int step) { //走越界了 if (x < 0 || x > 8 || y < 0 || y > 9){ return 0; } if (step == 0){ return (x == 0 && y == 0)?1:0; }else { return f1(x-1,y-2,step-1)+ f1(x-2,y-1,step-1)+ f1(x-2,y+1,step-1)+ f1(x-1,y+2,step-1)+ f1(x+1,y+2,step-1)+ f1(x+2,y+1,step-1)+ f1(x+2,y-1,step-1)+ f1(x+1,y-2,step-1); } } }

凑钱可能数
[x,y,z,c]其中x,yz,c是人民币面值，有任意张，aim为目标
【算法基础提升学习3】问：凑齐aim的可能数

/** * @Author: 郜宇博 * @Date: 2021/11/12 19:39 */ public class MoneyCounts { public static void main(String[] args) { System.out.println(getMoneyCount(new int[]{2, 3, 4, 10},50)); System.out.println(getMoneyCount1(new int[]{2, 3, 4, 10},50)); System.out.println(getMoneyCount2(new int[]{2, 3, 4, 10},50)); } public static int getMoneyCount(int[] arr, int aim){ return f(0,aim,arr); } public static int getMoneyCount1(int[] arr, int aim){ if (arr == null || arr.length == 0){ return 0; } //dp[index,rest] int[][] dp = new int[arr.length+1][aim+1]; dp[arr.length][0] = 1; //从下向上 for (int index = arr.length-1 ; index >= 0; index--){ for (int rest = 0; rest <= aim; rest++){ for (int i = 0; arr[index]*i <= rest; i++){ dp[index][rest] += dp[index+1][rest-arr[index]*i]; } } } return dp[0][aim]; } public static int getMoneyCount2(int[] arr, int aim){ if (arr == null || arr.length == 0){ return 0; } //dp[index,rest] int[][] dp = new int[arr.length+1][aim+1]; dp[arr.length][0] = 1; //从下向上 for (int index = arr.length-1 ; index >= 0; index--){ for (int rest = 0; rest <= aim; rest++){ dp[index][rest] = dp[index+1][rest]; if (rest-arr[index] >= 0){ dp[index][rest] += dp[index][rest-arr[index]]; } } } return dp[0][aim]; } public static int f(int index,int rest,int []arr){ if (index == arr.length){ return rest==0?1:0; } //有可用的钱，并且还没凑齐aim int res = 0; //i代表张数，尝试arr[index]位置的任意张数 for (int i = 0; i*arr[index]<=rest ; i++){ res += f(index+1,rest-arr[index]*i,arr); } return res; } }