[数据结构与算法]【蓝桥】算法 《拿金币》

【蓝桥】算法 《拿金币》

下面是我本人写的回溯算法，但是只有一个测试用例能通过，其他9个均超时，拜托各位大佬指点关于回溯中剪枝的操作，来降低递归深度并通过蓝桥OJ，同时也欢迎一起探讨！😃 😃 😃

import java.util.*;
public class _拿金币 {
	public static int sum = 0;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] money = new int[n][n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				money[i][j] = sc.nextInt();
			}
		} 	
		dfs(money, 0, 0, 0);
		System.out.println(sum);
	}
	// timeout 如何剪枝？？
	public static void dfs(int[][] m, int i, int j, int s) { // 使用回溯向下递归
		if (i < 0 || i >= m.length || j < 0 || j >= m.length
				|| j == m.length && i == m.length) {
			sum = Math.max(sum, s);
			return;
		}

		s += m[i][j];
		dfs(m, i+1,j, s);
		dfs(m, i, j+1, s);
		s -= m[i][j];
	}
}

测试用例运行结果：

1. 绿色为测试用例，黑色为运行结果

2. 绿色为测试用例，黑色为运行结果