地宫取宝(动态规划记忆性递归)

这道题是蓝桥杯2014年javaB的第九题。

题目链接

先写一个简单的递归答案

package B2014;import java.util.Scanner;public class B91 {//国王要求取宝的数量static int K = 0;//地宫的数据static int[][] data;//答案static long ans = 0;static int MOD = 1000000007;public static void main(String[] args) {//获取输入的数据存在data数组里Scanner scanner = new Scanner(System.in);int y = scanner.nextInt();int x = scanner.nextInt();K = scanner.nextInt();data = new int[y][x];for (int i = 0; i < data.length; i++) {for (int i1 = 0; i1 < data[i].length; i1++) {data[i][i1] = scanner.nextInt();}}dfs(0, -1, 0, 0);System.out.println(ans % MOD);}//k代表当前携带宝贝的数目//max代表当前携带宝贝最大的价值//x代表当前的列数//y代表当前的行数private static void dfs(int k, int max, int x, int y) {//递归防御/剪枝//如果y>=data.length||x>=data[0].length说明小明已经跨越地宫的边界，不符合要求//如果K>k说明，小明携带的宝物大于国王要求的数量，不符合要求if (y >= data.length || x >= data[0].length || k > K) {return;}//当前宝贝的价值int cur = data[y][x];//递归出口if (y == data.length - 1 && x == data[0].length - 1) {//小明在最后一个格子里，应该有两种情况可以放行//1，小明的宝物数量等于国王要求的数量//2，小明的宝物数量差一个等于国王宝物的数量，并且最后一个格子里的宝物价值大于小明任意宝贝价值if (k == K || (k == K - 1 && cur > max))ans++;}//如果当前宝贝的价值大于小明的手中任意宝贝，小明可以携带if (cur > max) {dfs(k + 1, cur, x, y + 1);dfs(k + 1, cur, x + 1, y);}//如果当前宝贝的价值小于等于于小明的手中任意宝贝，小明不可以携带dfs(k, max, x, y + 1);dfs(k, max, x + 1, y);}
}

这个是我用题目给出的例子
2 3 2
1 2 3
2 1 5
画出来的解析。

当然这样写肯定是要超时的，因为小明在每个格子上都面临四种选择(除了四个边上)，如果是五十乘五十的格子，那么小明要走一百步，4的100次方的数量级还是很大的。

这个时候就需要用到记忆性递归了。

package B2014;import java.util.Scanner;public class B9 {//国王要求取宝的数量static int K = 0;//地宫的数据static int[][] data;static int MOD = 1000000007;public static void main(String[] args) {//获取输入的数据存在data数组里Scanner scanner = new Scanner(System.in);int y = scanner.nextInt();int x = scanner.nextInt();K = scanner.nextInt();data = new int[y][x];for (int i = 0; i < data.length; i++) {for (int i1 = 0; i1 < data[i].length; i1++) {data [i][i1] = scanner.nextInt();}}//初始化记忆的数组for (int i = 0; i < ache.length; i++) {for (int j = 0; j < ache[0].length; j++) {for (int o = 0; o < ache[0][0].length; o++) {for (int p = 0; p < ache[0][0][0].length; p++) {ache [i] [j] [o] [p] = -1;}}}}System.out.println(dfs(0, -1, 0, 0)%MOD);}//用来记忆的数组static long [][][][] ache = new long[51][51][14][14];//k代表当前携带宝贝的数目//max代表当前携带宝贝最大的价值//x代表当前的列数//y代表当前的行数private static long dfs( int k, int max, int x, int y) {//答案long ans = 0;//查找缓存的数据if(ache[x][y][k][max+1]!= -1) return ache[x][y][k][max+1];//递归防御/剪枝//如果y>=data.length||x>=data[0].length说明小明已经跨越地宫的边界，不符合要求//如果K>k说明，小明携带的宝物大于国王要求的数量，不符合要求if(y>=data.length||x>=data[0].length||k>K){return 0;}//当前宝贝的价值int cur = data[y][x];//递归出口if(y==data.length-1&&x==data[0].length-1){//小明在最后一个格子里，应该有两种情况可以放行//1，小明的宝物数量等于国王要求的数量//2，小明的宝物数量差一个等于国王宝物的数量，并且最后一个格子里的宝物价值大于小明任意宝贝价值if (k == K || (k == K - 1 && cur > max))return 1;}//如果当前宝贝的价值大于小明的手中任意宝贝，小明可以携带if(cur>max){ans+=dfs(k+1,cur,x,y+1);ans+=dfs(k+1,cur,x+1,y);}//如果当前宝贝的价值小于等于于小明的手中任意宝贝，小明不可以携带ans+=dfs(k,max,x,y+1);ans+=dfs(k,max,x+1,y);//储存缓存的数据ache[x][y][k][max+1] = ans;return ans;}
}

记忆性递归的好处就是能把某个格子上到终点的路线存起来，比如我用红圈圈主的两个格子。第一次它会将该格子的数据存到数组中，那么第二次再访问这个格子的时候就不用计算，直接在数组中获取了。