【面试现场】如何编程获得最多的年终红包奖？

点击上方“ 程序人生 ”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

作者

channingbreeze

已获原作者授权，如需转载，请联系原作者。

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进 BAT 互联网公司。

今天小史又去了一家互联网小巨头公司面试了。

【面试现场】

小史眉头一皱，发现事情并不简单。

题目： 在数字矩阵中，从左上角到右下角，每次只能向右或向下，如何规划路径，能获得最大数字总和？

小史开始仔细分析问题，一时间竟想不到很好的方法。

小史心中反复默念题目，进行思考。

小史仔细回忆起了吕老师教他的华容道搜索算法。

【请教大神】

回到学校，小史把面试情况和吕老师说了一下。

吕老师：红色和蓝色两条路都能到达中间的1 00 这个点，但是很明显，红色的路拿到的奖金更多。所以蓝色的路，后面不管再怎么走，都不可能拿到最大的奖金数了。

吕老师：假设蓝色路径再往后走出一条绿色路径是最大奖金，那么我把蓝色路径替换成红色路径，红色加绿色得到的奖金就比蓝色加绿色得到的多呀。

【记忆化搜索】

小史：哦，我明白了，这样我每搜到一个点，都可以和这个数比较，如果比它大，就更新这个数，继续搜，如果比它小，就不搜了，直接剪枝。

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

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));

    }
}

(友情提示：可左右滑动)

运行结果

PS：这次这篇花费了两周时间。如果你看到了这里，并且有所收获的话，可以动动手指转发一下哦，小史和吕老师都会感谢你。

面试现场是互联网侦察推出的一个新的板块，旨在回放真实的面试过程，并对面试题进行全面解析，提供多种思路，比较优劣，希望对大家的面试有所帮助。

- The End -

「若你有原创文章想与大家分享，欢迎投稿。」

加编辑微信ID，备注#投稿#：

程序 丨 druidlost  

小七 丨 duoshangshuang

点文末 阅读全文 ，看『程序人生』其他精彩文章推荐。

免费公开课｜扫码即可报名 

想学习超级账本的同学千万不要错过！开课前报名可免费观看直播和回放，课程结束后只有会员才可免费观看回放哦！

推荐阅读：

• 107 岁的 IBM 以 340 亿美元吞下了 25 岁的“小”红帽！

• 影响 5000 万开发者，GitHub 与 CSDN 掌舵人对话技术社区未来

• 【有奖倒计时】带你走进AI应用创新大赛十强背后的故事！

• 40k~70k！京东这波区块链人才需求有你吗？你差在哪里？

• 只因会区块链，就被300个女孩疯追？马云：是真的！

• 盘点互联网大厂AI战略变迁，开发者将怎样pick前进路线？

print_r('点个赞吧')；
var_dump('点个赞吧')；
NSLog(@"点个赞吧！")
System.out.println("点个赞吧!");
console.log("点个赞吧!");
print("点个赞吧!");
printf("点个赞吧!\n");
cout << "点个赞吧!" << endl;
Console.WriteLine("点个赞吧!");
fmt.Println("点个赞吧!")
Response.Write("点个赞吧")；
alert（’点个赞吧’）