网站空间续费多少钱,常州网站建设团队,企业形象设计考试,wordpress会员介绍页机器人达到指定位置方法数
来自左程云老师书中的一道题
【题目】
假设有排成一行的 N 个位置#xff0c;记为 1~N#xff0c;N 一定大于或等于 2。开始时机器人在其中的 M
位置上#xff08;M 一定是 1#xff5e;N 中的一个#xff09;#xff0c;机器人可以往左走或…机器人达到指定位置方法数
来自左程云老师书中的一道题
【题目】
假设有排成一行的 N 个位置记为 1~NN 一定大于或等于 2。开始时机器人在其中的 M
位置上M 一定是 1N 中的一个机器人可以往左走或者往右走如果机器人来到 1 位置
那么下一步只能往右来到 2 位置如果机器人来到 N 位置那么下一步只能往左来到 N-1 位置。
规定机器人必须走 K 步最终能来到 P 位置P 也一定是 1N 中的一个的方法有多少种。给
定四个参数 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 process(int N,int M,int K, int P) {if(K 0) {return M P? 1:0;}if(M 1) {return process(N,M1,K-1,P);}if(M N) {return process(N,M-1,K-1,P);}return process(N,M1,K-1,P) process(N,M-1,K-1,P);}递归推导动态规划
前提判断是否是无后效性的。所谓无后效性是指是指一个递归状态的返回值与怎么到达这个状态的路径无关。
找到什么可变参数可以代表一个递归状态也就是那些参数一旦确定返回值也就确定了把可变参数的所有组合映射成一张表有1个可变参数就是一维表有2个可变参数就是一张二维表….最终答案要的是表中哪个位置在表中标出。根据递归的base case 把这张表最简单、不需要依赖其他位置的那些位置填好根据递归过程非base case的部分也就是分析表中的普遍位置需要怎么计算得到那么这张表的填写顺序也就确定了填好表返回最终答案在表中位置的值。
动态规划代码
public static int process2(int N,int M,int K, int P) {int[][] dp new int[K1][N1];dp[0][P] 1;for(int i 1;iK;i) {for(int j1;jN;j) {if(j1) {dp[i][j] dp[i-1][j1];} else if(j N) {dp[i][j] dp[i-1][j-1];} else {dp[i][j] dp[i-1][j1] dp[i-1][j-1];}}}return dp[K][M];}
