未来

用户名：tj16

访问量：3092

签　名：

等　　级
排　　名	4310
经　　验	1720
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	太原学院
专　　业

　　自我简介：

TA的其他文章

DNA-题解(Java代码)
浏览：214

DP和DFS+DP详解（Java代码）
浏览：1207

1451题约数倍数选卡片-题解(Java详解-博弈论）
浏览：597

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

DP和DFS+DP详解（Java代码）

　　作者: 未来　　　　发表时间：2020-02-02 19:03:42 浏览：1207　|　评论：1　

原题链接：蓝桥杯2014年第五届真题-地宫取宝

**解法一：** 动态规划
**子问题**
每个位置拿着k个宝物价值都低于g的方法
**确定状态**
map[i][j] (i,j)处的宝物价值
dp[i][j][sum][gold] (i,j)处拿着sum个宝物价值都低于gold 的方法数
则结果就是dp[n][m][k][12] 即出口处拿着k个宝物价值都低于12（价值0~12）的方法数
**边界状态**
在入口处，只有sum=1且gold>入口处宝物价值，或者sum=0，即入口可取时和不取两种情况下，有一可行方法：dp[i][j][sum][gold]=1，其余都为0 
因为首行首列也由继承而来，所以(i= =0||j= =0)的时候dp[i][j][sum][gold]=0，计数从1开始
**状态转移**
拿当前位置的宝物：(gold>map[i][j]&&sum>0)
YES= dp[i-1][j][k-1][sum-1][map[i][j]] (从上边继承)+dp[i][j-1][k-1][map[i][j]] (从左边继承)
不拿当前位置的宝物：
NO= dp[i-1][j][k][c] (从上边继承)+dp[i][j-1][k][c] (从左边继承)
则dp[i][j][k][c]= (YES+NO)

```java
package 蓝桥;

import java.util.Scanner;

public class Main {
	static int n;//行
	static int m;//列
	static int k;//需取数
	static int mod = 1000000007;//取余值
	static int dp[][][][] = new int[51][51][13][13];//x,y,已取数,最大价值
	static int map[][] = new int[51][51];//价值

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		k = sc.nextInt();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <m; j++) {
				map[i+1][j+1] = sc.nextInt();
			}
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				for(int s=0;s<=k;s++) {
					for(int g=0;g<13;g++) {
						int YES=0;
						int NO=0;
						if(i==1&&j==1){
				            if((s==0||(s==1&&g>map[i][j]))){
				            	dp[i][j][s][g]=1;
				            }
				            continue;
				        }
						if(s>0&&g>map[i][j]) {
							YES=dp[i-1][j][s-1][map[i][j]]+dp[i][j-1][s-1][map[i][j]];
							YES%=mod;
						}
				        NO=dp[i-1][j][s][g]+dp[i][j-1][s][g];
				        NO%=mod;
				        dp[i][j][s][g]=YES+NO;
				        dp[i][j][s][g]%=mod;
				    }
					}
				}
			}
		System.out.println(dp[n][m][k][12]);
		}
	}

```

**解法二：** 深度搜索+记忆化+动态规划
通过DFS从入口开始遍历所有的点，用动态规划计算该点可行方法数并记忆

```java
package 蓝桥;

import java.util.Scanner;

public class Main {
	static int n;//行
	static int m;//列
	static int k;//需取数
	static int mod = 1000000007;//取余值
	static int dp[][][][] = new int[50][50][15][15];//x,y,已取数,最大价值
	static int map[][] = new int[50][50];//价值

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		k = sc.nextInt();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		fill(dp，-1);//因为有的格子不能走，即方法数为0，避免重复搜索，全部置为-1
		System.out.println(dfs(0, 0, 0, -1));//最低价值为0，入口处可取可不取，因此初始最高价值置为-1
	}

static int dfs(int x, int y, int sum, int max) {
		//越界，比如一直向下一直向右，不可行
		if(x>=n||y>=m||sum>k) {
			return 0;
		}
		//入口的方法数已更新，即已经搜索完毕
		if(dp[x][y][sum][max+1]!=-1) {//因为max初值设为-1，不+1会下越界
			return dp[x][y][sum][max+1];
		}
		int count=0;//方法数
		int gold=map[x][y];//当前位置的价值
		if(x==n-1&&y==m-1) {//到达出口
			//如果已经有K个或者有k-1个且出口处的价值大于手中价值（即可以拿），即为一种可行方法
			if(sum==k||(sum==k-1&&gold>max)) {
				return 1;
			}
			//到达出口但是宝物不够，不可行
			return 0;
		}
		if(gold>max) {//此处可取，取之，每次相加时取余
			count+=dfs(x+1,y,sum+1,gold);
			count%=mod;
			count+=dfs(x,y+1,sum+1,gold);
			count%=mod;
		}
		//不取（不能取和可取但是没有取两种情况）
		count+=dfs(x+1,y,sum,max);
		count%=mod;
		count+=dfs(x,y+1,sum,max);
		count%=mod;
		//记忆
		dp[x][y][sum][max+1]=count;
		return count;
	}

static void fill(int[][][][] dp2) {
		for (int i = 0; i < 50; i++) {
			for (int j = 0; j < 50; j++) {
				for (int k = 0; k < 15; k++) {
					for (int l = 0; l < 15; l++) {
						dp[i][j][k][l] = -1;
					}
				}
			}
		}

}
}
```

0.0分

11 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

dotcpp0586235

请问为什么拿取宝物是gold>map[i][j],不是应该当前小于格子才能拿吗

2022-07-28 18:18:27

未来

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

DP和DFS+DP详解（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

关于C语言变量位置的问题

星期判断机（C语言代码）

Tom数（C语言代码）

1392题解(大数相加)

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

未来

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

DP和DFS+DP详解（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

关于C语言变量位置的问题

星期判断机 （C语言代码）

Tom数 （C语言代码）

1392题解(大数相加)

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

　　评论区

星期判断机（C语言代码）

Tom数（C语言代码）

C二级辅导-阶乘数列（C语言代码）