藍橋杯 2014年 第五屆 迷宮尋寶 詳解(JAVA)

基礎思路（DFS）

package provincial_2014B;

import java.util.Scanner;

/**
 * 該題有兩種做法：
 * 	- dfs + 剪枝： 雖有優化，但還是速度較慢，但好入門
 * 	- 動态規劃（記憶性深搜實作）：先搞清楚dfs，再了解dp
 *
 */
public class Nine {
	// 一般都把map數組定義為全局變量
	private static int n,m,k;
	private static int[][] map;
	private static final int MOD = 1000000007;
    // 題中告知要對MOD取餘，顯然較大，是以用long或double
	private static long ans;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		k = scan.nextInt();
		map = new int[n][m];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				map[i][j] = scan.nextInt();
			}
		}
		dfs(0, 0, 0, -1);
		System.out.println(ans);
	}

    // 需要注意的是：x是橫坐标，y是縱坐标，是以對應于數組的元素為map[y][x];
	private static void dfs(int x, int y, int goods, int max) {
		// 邊界預防
		if(x==m||y==n) {
			return;
		}
		int now = map[y][x];
		// 到達最終點
		// ***注意：到達最終點後由于不會再進行判斷拿不拿了
		// ***	      是以必須在這裡再判斷一次拿不拿
		if(x==m-1&&y==n-1) {
			if(goods==k || (goods==k-1&&max<now)) {
				ans++;
				ans %= MOD;
			}
			return;
		}
		
		// 拿了，向下或向右走
		if(max<now) {
			dfs(x, y+1, goods+1, now);
			dfs(x+1, y, goods+1, now);
		}
		// 沒拿，向下或向右走
		dfs(x+1, y, goods, max);
		dfs(x, y+1, goods, max);
	}
	
	
}

           

基礎思路優化（剪枝）

當goods（已拿的寶物）比最終要拿到的寶物還多時，就return（不走了）。

package provincial_2014B;

import java.util.Scanner;

/**
 * 該題有兩種做法：
 * 	- dfs + 剪枝： 雖有優化，但還是速度較慢，但好入門
 * 	- 動态規劃（記憶性深搜實作）：先搞清楚dfs，再了解dp
 *
 */
public class Nine {
	// 一般都把map數組定義為全局變量
	private static int n,m,k;
	private static int[][] map;
	private static final int MOD = 1000000007;
	private static long ans;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		k = scan.nextInt();
		map = new int[n][m];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				map[i][j] = scan.nextInt();
			}
		}
		dfs(0, 0, 0, -1);
		System.out.println(ans);
	}

    // 需要注意的是：x是橫坐标，y是縱坐标，是以對應于數組的元素為map[y][x];
	private static void dfs(int x, int y, int goods, int max) {
		// 邊界預防
		if(x==m||y==n||goods>k) {
			return;
		}
		int now = map[y][x];
		// 到達最終點
		// ***注意：到達最終點後由于不會再進行判斷拿不拿了
		// ***	      是以必須在這裡再判斷一次拿不拿
		if(x==m-1&&y==n-1) {
			if(goods==k || (goods==k-1&&max<now)) {
				ans++;
				ans %= MOD;
			}
			return;
		}
		
		// 拿了，向下或向右走
		if(max<now) {
			dfs(x, y+1, goods+1, now);
			dfs(x+1, y, goods+1, now);
		}
		// 沒拿，向下或向右走
		dfs(x+1, y, goods, max);
		dfs(x, y+1, goods, max);
	}
}

           

動态規劃/記憶型遞歸

其實記憶型遞歸就是在剛剛剪枝的基礎上再進行優化（剪枝）。

核心就是加入一個新數組cache用來緩存每一個子問題的解。其中，dfs有幾個參數，cache就有幾個次元。将每種情況看作一種狀态。

package provincial_2014B;

import java.util.Scanner;

/**
 * 該題有兩種做法：
 * 	- dfs + 剪枝： 雖有優化，但還是速度較慢，但好入門
 * 	- 動态規劃（記憶性深搜實作）：先搞清楚dfs，再了解dp
 *
 */
public class Nine {
	// 一般都把map數組定義為全局變量
	private static int n,m,k;
	private static int[][] map;
	private static final int MOD = 1000000007;
	// 開個數組反映一一映射關系
	private static long[][][][] cache;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		k = scan.nextInt();
		map = new int[n][m];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				map[i][j] = scan.nextInt();
			}
		}
		//***注意：因為寶物的價值一開始傳進去為-1，不滿足下标規則
		//***	  是以記錄時要+1，是以最大下标也要+1
		cache = new long[n][m][14][14];
		// 為什麼填充-1：因為ans有可能return0，在不滿足條件時，
		// 就可以看做該點已經走過，狀态為0
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				for(int r = 0; r < 14; r++)
					for(int q = 0; q < 14; q++)
						cache[i][j][r][q]=-1;
		long ans = dp(0, 0, 0, -1);
		System.out.println(ans);
	}

	private static long dp(int x, int y, int goods, int max) {
		// 邊界預防+剪枝
		if(x==m||y==n||goods>k) {
			return 0;
		}
		if(cache[y][x][goods][max+1]!=-1) return cache[y][x][goods][max+1];
		int now = map[y][x];
		
		// 某個點的傳回值（該點的狀态/該點拿了幾件貨物）
		// 由以下情況組成
		long ans = 0;
		
		// 到達最終點
		// ***注意：到達最終點後由于不會再進行判斷拿不拿了
		// ***	      是以必須在這裡再判斷一次拿不拿
		if(x==m-1&&y==n-1) {
			if(goods==k || (goods==k-1&&max<now)) {
				return 1;
			}
			return 0;
		}
		
		// 拿了，向下或向右走
		if(max<now) {
			ans += dp(x, y+1, goods+1, now);
			ans += dp(x+1, y, goods+1, now);
		}
		// 沒拿，向下或向右走
		ans += dp(x+1, y, goods, max);
		ans += dp(x, y+1, goods, max);
		
		// 記錄該點的值到緩存
		cache[y][x][goods][max+1] = ans % MOD;
		return cache[y][x][goods][max+1];
	}
}