其他
如何用编程 get 百万年终奖？
2018 年 CSDN 软件开发者大调查活动开始了！自 2004 年开始，我们通过对开发人员、开发技术以及开发工具、平台的状况和发展趋势等进行深入的调研，为开发者呈现了一幅幅真实的中国开发者画像。十四年的岁月沉淀，万余人的浓墨重彩。相信有你的参与，会让这幅开发者绘卷更加精彩。“Stay hungry, stay foolish”——Just join us now！
（继续下滑，阅读精彩内容吧 ↓）
作者| 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
作者简介：channingbreeze，国内某互联网公司全栈开发。
声明：本文为作者投稿，版权归对方所有。作者独立观点，不代表 CSDN 立场。
微信改版了，
想快速看到CSDN的热乎文章，
赶快把CSDN公众号设为星标吧，
打开公众号，点击“设为星标”就可以啦！
“征稿啦”
CSDN 公众号秉持着「与千万技术人共成长」理念，不仅以「极客头条」、「畅言」栏目在第一时间以技术人的独特视角描述技术人关心的行业焦点事件，更有「技术头条」专栏，深度解读行业内的热门技术与场景应用，让所有的开发者紧跟技术潮流，保持警醒的技术嗅觉，对行业趋势、技术有更为全面的认知。
如果你有优质的文章，或是行业热点事件、技术趋势的真知灼见，或是深度的应用实践、场景方案等的新见解，欢迎联系 CSDN 投稿，联系方式：微信（guorui_1118，请备注投稿+姓名+公司职位），邮箱（guorui@csdn.net）。
推荐阅读：