【面试现场】如何编程获得最多的年终红包奖？
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。
今天小史又去了一家互联网小巨头公司面试了。
【面试现场】
小史眉头一皱，发现事情并不简单。
题目：在数字矩阵中，从左上角到右下角，每次只能向右或向下，如何规划路径，能获得最大数字总和？
小史开始仔细分析问题，一时间竟想不到很好的方法。
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
小史心中反复默念题目，进行思考。
小史仔细回忆起了吕老师教他的华容道搜索算法。
【请教大神】
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
回到学校，小史把面试情况和吕老师说了一下。
吕老师：红色和蓝色两条路都能到达中间的100这个点，但是很明显，红色的路拿到的奖金更多。所以蓝色的路，后面不管再怎么走，都不可能拿到最大的奖金数了。
吕老师：假设蓝色路径再往后走出一条绿色路径是最大奖金，那么我把蓝色路径替换成红色路径，红色加绿色得到的奖金就比蓝色加绿色得到的多呀。
【记忆化搜索】
小史：哦，我明白了，这样我每搜到一个点，都可以和这个数比较，如果比它大，就更新这个数，继续搜，如果比它小，就不搜了，直接剪枝。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
DeepFirstSearch.java
Main.java
运行结果
【记忆广搜】
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
吕老师：记忆深搜确实可以剪枝，但是假如有人刻意安排数字，把较小的数都安排在你先搜的路径上，那么你的计算量还是不会减少太多。
小史：还有这么坏的人呢？不过你这样一说我到想起来，深搜确实缺少一种“全局观”，可能第一条路搜完了，再来看第二条路，发现更好，结果第一条路全白搜了。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
BreadthFirstSearch.java
Main.java
【动态规划】
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
吕老师：小史，代码写得不错，咱们再来看看广搜的过程，其实就是在搜索的过程中从左上到右下计算出了best(i,j)，所以为啥我们不能直接算出best(i,j)呢？
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
Main.java
【动态规划解析】
吕老师：状态的定义要满足几个点，第一，问题的答案是某种状态，或者可由状态进行推导。第二，当前状态可以由之前的状态推导而来。
【状态压缩】
小史：哦，我知道了，这道题，如果按照斜线方向来计算，只需要保留一条斜线的状态，就能计算出下一条斜线。所以之前的状态就不需要保留了。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
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)
privatevoidcalcDp(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];
}
}
}
// 获取最大值
publicintgetMaxAward(int[][] matrix){
calcDp(matrix);
return best[0][0];
}
}
Main.java
PS：这次这篇花费了两周时间。如果你看到了这里，并且有所收获的话，可以动动手指转发一下哦，非常感谢！
给大家推荐一个程序员学习交流群：854818273。群里有分享的视频，还有思维导图
群公告有视频，都是干货的，你可以下载来看。主要分享分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频。
