点击蓝色“五分钟学算法”关注我哟
加个“星标”，天天中午 12:15，一起学算法
作者 | channingbreeze
来源 | 互联网侦察
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。
今天小史又去了一家互联网小巨头公司面试了。
【面试现场】
小史眉头一皱，发现事情并不简单。
题目：在数字矩阵中，从左上角到右下角，每次只能向右或向下，如何规划路径，能获得最大数字总和？
小史开始仔细分析问题，一时间竟想不到很好的方法。
小史心中反复默念题目，进行思考。
小史仔细回忆起了吕老师教他的华容道搜索算法。
【请教大神】
回到学校，小史把面试情况和吕老师说了一下。
吕老师：红色和蓝色两条路都能到达中间的100这个点，但是很明显，红色的路拿到的奖金更多。所以蓝色的路，后面不管再怎么走，都不可能拿到最大的奖金数了。
吕老师：假设蓝色路径再往后走出一条绿色路径是最大奖金，那么我把蓝色路径替换成红色路径，红色加绿色得到的奖金就比蓝色加绿色得到的多呀。
【记忆化搜索】
小史：哦，我明白了，这样我每搜到一个点，都可以和这个数比较，如果比它大，就更新这个数，继续搜，如果比它小，就不搜了，直接剪枝。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
DeepFirstSearch.java
import java.util.ArrayList;
import java.util.List;
/**
* @author xiaoshi on 2018/10/20.
*/
public class DeepFirstSearch {
// 定义best(i,j) 和 M N
private int[][] best = null;
private int M = 0;
private int N = 0;
// 定义方向常量
private static final int RIGHT = 1;
private static final int DOWN = 2;
// 当前搜索的方向数组
private List<Integer> curPath = null;
// 记录最大值对应的方向数组
private Integer[] bestPath = null;
// 当前搜索点
private int curX = 0;
private int curY = 0;
// 当前搜索累计值
private int value = 0;
// 记录搜索到的最大值
private int maxValue = 0;
// 往某个方向前进
private void goDir(int dir, int[][] matrix) {
// 前进
if(dir == DOWN) {
curX++;
value += matrix[curX][curY];
} else if(dir == RIGHT) {
curY++;
value += matrix[curX][curY];
}
// 记录方向
curPath.add(dir);
}
// 往某个方向回退
private void goBackDir(int dir, int[][] matrix) {
// 回退
if(dir == DOWN) {
value -= matrix[curX][curY];
curX--;
} else if(dir == RIGHT) {
value -= matrix[curX][curY];
curY--;
}
// 移除方向
curPath.remove(curPath.size() - 1);
}
// 深搜
private void search(int dir, int[][] matrix) {
// 往某方向前进
goDir(dir, matrix);
// 到达终点
if(curX == M - 1 && curY == N - 1) {
if(value > maxValue) {
// 记录最大值和路径
maxValue = value;
bestPath = new Integer[curPath.size()];
curPath.toArray(bestPath);
}
} else if(value <= best[curX][curY]) {
// 不搜索了，等着goBack，剪枝
} else {
// 更新best(i,j)，记忆
best[curX][curY] = value;
// 朝下一个方向搜索
if(curX < M - 1) {
search(DOWN, matrix);
}
if(curY < N - 1) {
search(RIGHT, matrix);
}
}
// 往某方向回退
goBackDir(dir, matrix);
}
// 获取最大值
public int getMaxAward(int[][] matrix) {
// 初始化
value = matrix[0][0];
M = matrix.length;
N = matrix[0].length;
best = new int[M][N];
curPath = new ArrayList<Integer>();
// 开始搜索
if(M > 1) {
search(DOWN, matrix);
}
if(N > 1) {
search(RIGHT, matrix);
}
// 最大值
return maxValue;
}
// 打印最佳路径
public void printBestPath() {
// 打印路径
for(int i = 0; i < bestPath.length; i++) {
if(bestPath[i] == RIGHT) {
System.out.print("右 ");
} else {
System.out.print("下 ");
}
}
System.out.println();
}
}
(友情提示：可左右滑动)
Main.java
/**
* @author xiaoshi on 2018/10/20.
*/
public class Main {
public static void main(String[] args) {
int[][] matrix1 = {
{300, 500, 560, 400, 160},
{1000, 100, 200, 340, 690},
{600, 500, 500, 460, 320},
{300, 400, 250, 210, 760}
};
int[][] matrix2 = {
{300, 500, 2560, 400},
{1000, 100, 200, 340},
{600, 500, 500, 460},
{300, 400, 250, 210},
{860, 690, 320, 760}
};
DeepFirstSearch dp = new DeepFirstSearch();
System.out.println(dp.getMaxAward(matrix1));
dp.printBestPath();
System.out.println(dp.getMaxAward(matrix2));
dp.printBestPath();
}
}
(友情提示：可左右滑动)
运行结果
4440
下 下 右 右 右 右 下
5530
右 右 右 下 下 下 下
【记忆广搜】
吕老师：记忆深搜确实可以剪枝，但是假如有人刻意安排数字，把较小的数都安排在你先搜的路径上，那么你的计算量还是不会减少太多。
小史：还有这么坏的人呢？不过你这样一说我到想起来，深搜确实缺少一种“全局观”，可能第一条路搜完了，再来看第二条路，发现更好，结果第一条路全白搜了。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
BreadthFirstSearch.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @author xiaoshi on 2018/10/20.
*/
public class BreadthFirstSearch {
// 定义 M N
private int M = 0;
private int N = 0;
// 定义方向常量
private static final int RIGHT = 1;
private static final int DOWN = 2;
// 代表广搜的每一步，通过lastItem链起来
private class SearchItem {
private int curX;
private int curY;
private int dir;
// 这里记录 (curX, curY) 路径的最大值，相当于best(i,j)
private int value;
private SearchItem lastItem;
public SearchItem(int curX, int curY, int dir, int value) {
this.curX = curX;
this.curY = curY;
this.dir = dir;
this.value = value;
}
}
// 最终搜到的结果
private SearchItem bestItem = null;
// 广搜的存储队列
private List<SearchItem> statusToSearch = new LinkedList<SearchItem>();
// 替换广搜队列中较小的item，返回值为搜索队列中是否找到相应item
private boolean replaceStatusList(SearchItem newItem) {
// 是否找到
boolean find = false;
// 遍历查找
for(int i=0; i<statusToSearch.size(); i++) {
SearchItem searchItem = statusToSearch.get(i);
// 找到对应item
if(searchItem.curX == newItem.curX && searchItem.curY == searchItem.curY) {
find = true;
// 这里相当于在对比best(i,j)
if(searchItem.value < newItem.value) {
// 替换成更好的item
statusToSearch.remove(i);
statusToSearch.add(i, newItem);
}
break;
}
}
return find;
}
// 广搜
private void search(int[][] matrix) {
// 搜索队列中不为空
while(statusToSearch.size() > 0) {
// 从搜索队列中获取一个item
SearchItem searchItem = statusToSearch.remove(0);
int curX = searchItem.curX;
int curY = searchItem.curY;
int curValue = searchItem.value;
// 如果已经搜到
if(curX == M - 1 && curY == N - 1) {
bestItem = searchItem;
}
// 可往下搜
if(curX < M - 1) {
SearchItem newItem = new SearchItem(curX + 1, curY, DOWN, curValue + matrix[curX + 1][curY]);
newItem.lastItem = searchItem;
// 是否替代
if(!replaceStatusList(newItem)) {
// 搜索队列中没有找到，则添加
statusToSearch.add(newItem);
}
}
// 可往右搜
if(curY < N - 1) {
SearchItem newItem = new SearchItem(curX, curY + 1, RIGHT, curValue + matrix[curX][curY + 1]);
newItem.lastItem = searchItem;
// 是否替代
if(!replaceStatusList(newItem)) {
// 搜索队列中没有找到，则添加
statusToSearch.add(newItem);
}
}
}
}
// 获取最大值
public int getMaxAward(int[][] matrix) {
// 初始化
M = matrix.length;
N = matrix[0].length;
int value = matrix[0][0];
SearchItem searchItem = new SearchItem(0, 0, 0, value);
statusToSearch.add(searchItem);
// 开始搜索
search(matrix);
// 返回最大值
return bestItem.value;
}
// 打印最佳路径
public void printBestPath() {
List<Integer> dirList = new ArrayList<Integer>();
SearchItem curSearchItem = bestItem;
// 根据lastItem，找到路径
while(null != curSearchItem) {
int dir = curSearchItem.dir;
if(dir == DOWN) {
dirList.add(DOWN);
} else if(dir == RIGHT) {
dirList.add(RIGHT);
}
curSearchItem = curSearchItem.lastItem;
}
// 打印路径
for(int i = dirList.size() - 1; i >= 0; i--) {
if(dirList.get(i) == DOWN) {
System.out.print("下 ");
} else if(dirList.get(i) == RIGHT) {
System.out.print("右 ");
}
}
System.out.println();
}
}
(友情提示：可左右滑动)
Main.java
/**
* @author xiaoshi on 2018/10/20.
*/
public class Main {
public static void main(String[] args) {
int[][] matrix1 = {
{300, 500, 560, 400, 160},
{1000, 100, 200, 340, 690},
{600, 500, 500, 460, 320},
{300, 400, 250, 210, 760}
};
int[][] matrix2 = {
{300, 500, 2560, 400},
{1000, 100, 200, 340},
{600, 500, 500, 460},
{300, 400, 250, 210},
{860, 690, 320, 760}
};
BreadthFirstSearch dp = new BreadthFirstSearch();
System.out.println(dp.getMaxAward(matrix1));
dp.printBestPath();
System.out.println(dp.getMaxAward(matrix2));
dp.printBestPath();
}
}
(友情提示：可左右滑动)
运行结果
4440
下 下 右 右 右 右 下
5530
右 右 右 下 下 下 下
【动态规划】
吕老师：小史，代码写得不错，咱们再来看看广搜的过程，其实就是在搜索的过程中从左上到右下计算出了best(i,j)，所以为啥我们不能直接算出best(i,j)呢？
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
DynamicProgramming.java
import java.util.ArrayList;
import java.util.List;
/**
* @author xiaoshi on 2018/10/20.
*/
public class DynamicProgramming {
// 定义best(i,j) 和 M N
private int[][] best = null;
private int M = 0;
private int N = 0;
// 定义方向常量
private static final int RIGHT = 1;
private static final int DOWN = 2;
// 存储最好路径
private List<Integer> bestPath = null;
// 计算best(i,j)
private void calcDp(int[][] matrix) {
// 初始化
M = matrix.length;
N = matrix[0].length;
best = new int[M][N];
// 计算
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
// 边界
if(i == 0 && j == 0) {
best[i][j] = matrix[i][j];
} else if(i == 0) {
best[i][j] = best[i][j - 1] + matrix[i][j];
} else if(j == 0) {
best[i][j] = best[i - 1][j] + matrix[i][j];
} else {
// 状态转移
best[i][j] = Math.max(best[i - 1][j], best[i][j - 1]) + matrix[i][j];
}
}
}
}
// 获取最大值
public int getMaxAward(int[][] matrix) {
// 计算状态
calcDp(matrix);
// 计算最佳路径
calcBestPath();
// 返回最大值
return best[matrix.length - 1][matrix[0].length - 1];
}
// 计算最佳路径，从后往前
private void calcBestPath() {
bestPath = new ArrayList<Integer>();
// 总共走 M + N - 2 步
int curX = M - 1;
int curY = N - 1;
// 根据best(i,j)计算最佳路径
for(int i = 0; i < M + N - 2; i++) {
if(curX == 0) {
curY--;
bestPath.add(RIGHT);
} else if(curY == 0) {
curX--;
bestPath.add(DOWN);
} else {
if(best[curX - 1][curY] > best[curX][curY - 1]) {
curX--;
bestPath.add(DOWN);
} else {
curY--;
bestPath.add(RIGHT);
}
}
}
}
// 打印最佳路径
public void printBestPath() {
// 倒序打印
for(int i = bestPath.size() - 1; i >= 0; i--) {
if(bestPath.get(i) == RIGHT) {
System.out.print("右 ");
} else {
System.out.print("下 ");
}
}
System.out.println();
}
}
(友情提示：可左右滑动)
Main.java
/**
* @author xiaoshi on 2018/10/20.
*/
public class Main {
public static void main(String[] args) {
int[][] matrix1 = {
{300, 500, 560, 400, 160},
{1000, 100, 200, 340, 690},
{600, 500, 500, 460, 320},
{300, 400, 250, 210, 760}
};
int[][] matrix2 = {
{300, 500, 2560, 400},
{1000, 100, 200, 340},
{600, 500, 500, 460},
{300, 400, 250, 210},
{860, 690, 320, 760}
};
DynamicProgramming dp = new DynamicProgramming();
System.out.println(dp.getMaxAward(matrix1));
dp.printBestPath();
System.out.println(dp.getMaxAward(matrix2));
dp.printBestPath();
}
}
(友情提示：可左右滑动)
运行结果
4440
下 下 右 右 右 右 下
5530
右 右 右 下 下 下 下
【动态规划解析】
吕老师：状态的定义要满足几个点，第一，问题的答案是某种状态，或者可由状态进行推导。第二，当前状态可以由之前的状态推导而来。
【状态压缩】
小史：哦，我知道了，这道题，如果按照斜线方向来计算，只需要保留一条斜线的状态，就能计算出下一条斜线。所以之前的状态就不需要保留了。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
DpCompressed.java
/**
* @author xiaoshi on 2018/10/20.
*/
public class DpCompressed {
// 定义best(i) 和 M N
private int[][] best = null;
private int M = 0;
private int N = 0;
// 计算best(i)
private void calcDp(int[][] matrix) {
// 初始化
M = matrix.length;
N = matrix[0].length;
int minMN = Math.min(M, N);
int maxMN = Math.max(M, N);
// best只需要M和N的最小值长度就行
best = new int[2][minMN];
// 需要计算 M+N-1 条斜线
for(int i = 0; i < M + N - 1; i++) {
// 第 i 条斜线的起始x坐标
int startX = 0;
// 第 i 条斜线的起始y坐标
int startY = i;
// 第 i 条斜线的数字个数
int number = i + 1;
if(i >= N) {
startX = i + 1 - N;
startY = N - 1;
}
if(i >= minMN) {
number = minMN;
}
if(i >= maxMN) {
number = M + N - i - 1;
}
// 第 i 条斜线上的 number 个数
for(int j = 0; j < number; j++) {
// 起始点
if(i == 0 && j == 0) {
best[1][j] = matrix[startX + j][startY - j];
} else {
if (i < N) {
// 前半部分
if (j == 0) {
// 上边界
best[1][j] = best[0][j] + matrix[startX + j][startY - j];
} else if (j == number - 1) {
// 左边界
best[1][j] = best[0][j-1] + matrix[startX + j][startY - j];
} else {
// 状态转移
best[1][j] = Math.max(best[0][j], best[0][j-1]) + matrix[startX + j][startY - j];
}
} else {
// 后半部分
if(i < M && j == number - 1) {
// 左边界
best[1][j] = best[0][j] + matrix[startX + j][startY - j];
} else {
// 状态转移
best[1][j] = Math.max(best[0][j], best[0][j+1]) + matrix[startX + j][startY - j];
}
}
}
}
// 将best[1]上的状态拷贝到best[0]
for(int j = 0; j < number; j++) {
best[0][j] = best[1][j];
}
}
}
// 获取最大值
public int getMaxAward(int[][] matrix) {
calcDp(matrix);
return best[0][0];
}
}
(友情提示：可左右滑动)
Main.java
/**
* @author xiaoshi on 2018/10/20.
*/
public class Main {
public static void main(String[] args) {
int[][] matrix1 = {
{300, 500, 560, 400, 160},
{1000, 100, 200, 340, 690},
{600, 500, 500, 460, 320},
{300, 400, 250, 210, 760}
};
int[][] matrix2 = {
{300, 500, 2560, 400},
{1000, 100, 200, 340},
{600, 500, 500, 460},
{300, 400, 250, 210},
{860, 690, 320, 760}
};
DpCompressed dp = new DpCompressed();
System.out.println(dp.getMaxAward(matrix1));
System.out.println(dp.getMaxAward(matrix2));
}
}
(友情提示：可左右滑动)
运行结果
4440
5530
PS：这次这篇花费了两周时间。如果你看到了这里，并且有所收获的话，可以动动手指转发一下哦，小史和吕老师都会感谢你。
原文始发于微信公众号（五分钟学算法）：【面试现场】如何编程获得最多的年终红包奖？
