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

本是古典何须时尚 2023-06-12 14:26 17阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | channingbreeze

来源 | 互联网侦察

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

**【面试现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 21]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 22]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 23]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 24]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 25]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 26]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 27]

**【请教大神】**

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 28]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 29]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 30]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 31]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 32]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 33]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 34]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 35]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 36]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 37]

**【记忆化搜索】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 38]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 39]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 40]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 41]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 42]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 43]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 44]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 45]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 46]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 47]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 48]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 49]

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

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
    右 右 右 下 下 下 下

**【记忆广搜】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 50]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 51]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 52]

吕老师：记忆深搜确实可以剪枝，但是假如有人刻意安排数字，把较小的数都安排在你先搜的路径上，那么你的计算量还是不会减少太多。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 53]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 54]

小史：还有这么坏的人呢？不过你这样一说我到想起来，深搜确实缺少一种“全局观”，可能第一条路搜完了，再来看第二条路，发现更好，结果第一条路全白搜了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 55]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 56]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 57]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 58]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 59]

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

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
    右 右 右 下 下 下 下

**【动态规划】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 60]

吕老师：小史，代码写得不错，咱们再来看看广搜的过程，其实就是在搜索的过程中从左上到右下计算出了best(i,j)，所以为啥我们不能直接算出best(i,j)呢？

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 61]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 62]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 63]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 64]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 65]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 66]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 67]

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

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
    右 右 右 下 下 下 下

**【动态规划解析】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 68]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 69]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 70]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 71]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 72]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 73]

吕老师：状态的定义要满足几个点，第一，问题的答案是某种状态，或者可由状态进行推导。第二，当前状态可以由之前的状态推导而来。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 74]

**【状态压缩】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 75]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 76]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 77]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 78]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 79]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 80]

小史：哦，我知道了，这道题，如果按照斜线方向来计算，只需要保留一条斜线的状态，就能计算出下一条斜线。所以之前的状态就不需要保留了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 81]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 82]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 83]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 84]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 85]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 86]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 87]

--------------------

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

--------------------

**-----------------------**

**公众号：五分钟学算法** **（ID：CXYxiaowu** **）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力 **。**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 88]

[640_wx_fmt_jpeg]: https://img-blog.csdnimg.cn/img_convert/05e6d8ff5ce609efccbd8ecf502bc51c.png
[640_wx_fmt_jpeg 1]: https://img-blog.csdnimg.cn/img_convert/1ba4e64f726a991fd131543331537708.png
[640_wx_fmt_jpeg 2]: https://img-blog.csdnimg.cn/img_convert/d213e93a20cfaf60d524a7b15d7c5ff0.png
[640_wx_fmt_jpeg 3]: https://img-blog.csdnimg.cn/img_convert/e2a7a083b9c07197993a72523cacba25.png
[640_wx_fmt_jpeg 4]: https://img-blog.csdnimg.cn/img_convert/05da81ecb7c2a2ec0f2d051c684889a1.png
[640_wx_fmt_jpeg 5]: https://img-blog.csdnimg.cn/img_convert/b42704a1fa20f3d95080fec371ab2a5e.png
[640_wx_fmt_jpeg 6]: https://img-blog.csdnimg.cn/img_convert/dea41c0e3f9b7cbfafa73aebbdfd7c63.png
[640_wx_fmt_jpeg 7]: https://img-blog.csdnimg.cn/img_convert/d746e312c8b0f0e909a03f307b271c8a.png
[640_wx_fmt_jpeg 8]: https://img-blog.csdnimg.cn/img_convert/67d754228e9362d8edda9990b8e718e3.png
[640_wx_fmt_jpeg 9]: https://img-blog.csdnimg.cn/img_convert/84ff1bb6de92b674de471ee1e45c3619.png
[640_wx_fmt_jpeg 10]: https://img-blog.csdnimg.cn/img_convert/729d0c8e567cc8b12a2de8c1569e8539.png
[640_wx_fmt_jpeg 11]: https://img-blog.csdnimg.cn/img_convert/f8f9d04f4c40b6126595f5b8b23d90e0.png
[640_wx_fmt_jpeg 12]: https://img-blog.csdnimg.cn/img_convert/ad453605ebec92c33eb1d8e11a8a45d7.png
[640_wx_fmt_jpeg 13]: https://img-blog.csdnimg.cn/img_convert/bb85c9406ed975144261193cd579511d.png
[640_wx_fmt_jpeg 14]: https://img-blog.csdnimg.cn/img_convert/338d0120de0d396577d38234bcf831a5.png
[640_wx_fmt_jpeg 15]: https://img-blog.csdnimg.cn/img_convert/8a388066f93d60d0fbda360b50826b03.png
[640_wx_fmt_jpeg 16]: https://img-blog.csdnimg.cn/img_convert/85302eaeee8c4e045a7abef304ad8dd3.png
[640_wx_fmt_jpeg 17]: https://img-blog.csdnimg.cn/img_convert/99b3c33da1b61def8320e80cdab79b45.png
[640_wx_fmt_jpeg 18]: https://img-blog.csdnimg.cn/img_convert/552113913465d12ebc017773d72e8266.png
[640_wx_fmt_jpeg 19]: https://img-blog.csdnimg.cn/img_convert/2e16d45080f68f40df3983ce2c5d4273.png
[640_wx_fmt_jpeg 20]: https://img-blog.csdnimg.cn/img_convert/781eca7dfd73338ad13a31836977e162.png
[640_wx_fmt_jpeg 21]: https://img-blog.csdnimg.cn/img_convert/60dd1d655bed97cf10889e018bd6710d.png
[640_wx_fmt_jpeg 22]: https://img-blog.csdnimg.cn/img_convert/5acdc44ccd0491da6e99d3d562023e4f.png
[640_wx_fmt_jpeg 23]: https://img-blog.csdnimg.cn/img_convert/d91391b36fe9aa042db5f53b6b7195bf.png
[640_wx_fmt_jpeg 24]: https://img-blog.csdnimg.cn/img_convert/44bf6ac922d2e5fbe4a63638fcdf3e8f.png
[640_wx_fmt_jpeg 25]: https://img-blog.csdnimg.cn/img_convert/19314b6973b790391ae26443f5e2e503.png
[640_wx_fmt_jpeg 26]: https://img-blog.csdnimg.cn/img_convert/e9b912c53b23cac23954ff563b211b24.png
[640_wx_fmt_jpeg 27]: https://img-blog.csdnimg.cn/img_convert/4b79a954de6488485d22fc50b67de106.png
[640_wx_fmt_jpeg 28]: https://img-blog.csdnimg.cn/img_convert/4593553fe55a71c6c55742155fc63013.png
[640_wx_fmt_jpeg 29]: https://img-blog.csdnimg.cn/img_convert/a15aa7dd36d5a76fc95e0f1acf1a01f2.png
[640_wx_fmt_jpeg 30]: https://img-blog.csdnimg.cn/img_convert/6d708cf5ea6706db8051fc36b6f16ffc.png
[640_wx_fmt_jpeg 31]: https://img-blog.csdnimg.cn/img_convert/3e49080fd68c65188f7015441d4f54ff.png
[640_wx_fmt_jpeg 32]: https://img-blog.csdnimg.cn/img_convert/fe6b2f98f39dfac304c5cbbf788c1cbf.png
[640_wx_fmt_jpeg 33]: https://img-blog.csdnimg.cn/img_convert/d5d3299fff3c48104b3e18775a629925.png
[640_wx_fmt_jpeg 34]: https://img-blog.csdnimg.cn/img_convert/16425cc7e2160f96e5edbf991017caa2.png
[640_wx_fmt_jpeg 35]: https://img-blog.csdnimg.cn/img_convert/b4f14a511cfba9bf0e8559dc19fb2026.png
[640_wx_fmt_jpeg 36]: https://img-blog.csdnimg.cn/img_convert/f56ab0be9bd82bf64d7279ffc8766809.png
[640_wx_fmt_jpeg 37]: https://img-blog.csdnimg.cn/img_convert/382581794577f76e86aaf9cdc912ef6e.png
[640_wx_fmt_jpeg 38]: https://img-blog.csdnimg.cn/img_convert/b650f3e6062d679a9c0d3414e45e280e.png
[640_wx_fmt_jpeg 39]: https://img-blog.csdnimg.cn/img_convert/389c3163dcae48da1c2888f2db656c1a.png
[640_wx_fmt_jpeg 40]: https://img-blog.csdnimg.cn/img_convert/6bcee2d1b61c3ca4cf9b226e3c1e4410.png
[640_wx_fmt_jpeg 41]: https://img-blog.csdnimg.cn/img_convert/7da731ca99bc55ff8775c7956f8c9498.png
[640_wx_fmt_jpeg 42]: https://img-blog.csdnimg.cn/img_convert/9532e7ac50b2533ac692ebc10eba4d8f.png
[640_wx_fmt_jpeg 43]: https://img-blog.csdnimg.cn/img_convert/3f2bf2f6f85ba22ddd90d452366ffeb3.png
[640_wx_fmt_jpeg 44]: https://img-blog.csdnimg.cn/img_convert/bd33cd0be47005c5a2f11316d72e4152.png
[640_wx_fmt_jpeg 45]: https://img-blog.csdnimg.cn/img_convert/7f245d0b00ccee58703c511f2162f311.png
[640_wx_fmt_jpeg 46]: https://img-blog.csdnimg.cn/img_convert/b5c39eb2734cfd26598fd8678195e745.png
[640_wx_fmt_jpeg 47]: https://img-blog.csdnimg.cn/img_convert/1088eef859cfd3e6c43dacba4aab067a.png
[640_wx_fmt_jpeg 48]: https://img-blog.csdnimg.cn/img_convert/4fbd4bafbd1a96fc753fd4ea5d611b83.png
[640_wx_fmt_jpeg 49]: https://img-blog.csdnimg.cn/img_convert/d7f09141d8fc5969e079a383ffc590d2.png
[640_wx_fmt_jpeg 50]: https://img-blog.csdnimg.cn/img_convert/dfaf28ad5c22037a19fef315ff0cd105.png
[640_wx_fmt_jpeg 51]: https://img-blog.csdnimg.cn/img_convert/e34baf5a5b00f8ad68903977abf8c4ca.png
[640_wx_fmt_jpeg 52]: https://img-blog.csdnimg.cn/img_convert/ca664217b02dd21ffa8867b3fcb6450c.png
[640_wx_fmt_jpeg 53]: https://img-blog.csdnimg.cn/img_convert/b7237fea75604ffa03b415a00aae90bc.png
[640_wx_fmt_jpeg 54]: https://img-blog.csdnimg.cn/img_convert/d2b321a661b2846e6021c196c0facc7c.png
[640_wx_fmt_jpeg 55]: https://img-blog.csdnimg.cn/img_convert/ca747b42ddc473f743bfb3995d0bbecb.png
[640_wx_fmt_jpeg 56]: https://img-blog.csdnimg.cn/img_convert/d6e50e61cd19263b0060c31cc1cbc95b.png
[640_wx_fmt_jpeg 57]: https://img-blog.csdnimg.cn/img_convert/18e73919f8fe82455d4ca46e08085a6e.png
[640_wx_fmt_jpeg 58]: https://img-blog.csdnimg.cn/img_convert/f9e557caeabe534a62d29dea9f141a58.png
[640_wx_fmt_jpeg 59]: https://img-blog.csdnimg.cn/img_convert/f7c99662b4f5f597835487b37a934590.png
[640_wx_fmt_jpeg 60]: https://img-blog.csdnimg.cn/img_convert/e6bc45b8d9684485c1ecbd24be760176.png
[640_wx_fmt_jpeg 61]: https://img-blog.csdnimg.cn/img_convert/605b020174948a9603838d2015d3fee5.png
[640_wx_fmt_jpeg 62]: https://img-blog.csdnimg.cn/img_convert/f293eb0aa00ba50a92719aad36488271.png
[640_wx_fmt_jpeg 63]: https://img-blog.csdnimg.cn/img_convert/6e756fa93019eab000ce616be732066b.png
[640_wx_fmt_jpeg 64]: https://img-blog.csdnimg.cn/img_convert/16612a8b8dc08685c40b328ebd061845.png
[640_wx_fmt_jpeg 65]: https://img-blog.csdnimg.cn/img_convert/f413ef8c7aac5b6b5b0142876afd3cd5.png
[640_wx_fmt_jpeg 66]: https://img-blog.csdnimg.cn/img_convert/8376d2f3cb30adbd621fe728d6c21cda.png
[640_wx_fmt_jpeg 67]: https://img-blog.csdnimg.cn/img_convert/9ef1fff2d9f54a35944dd5935a9ac1c0.png
[640_wx_fmt_jpeg 68]: https://img-blog.csdnimg.cn/img_convert/fce5319ae501ac00df4d31ec976f98c6.png
[640_wx_fmt_jpeg 69]: https://img-blog.csdnimg.cn/img_convert/12fe209cf43b9951f31ad39fdbd04638.png
[640_wx_fmt_jpeg 70]: https://img-blog.csdnimg.cn/img_convert/12f9b304d347ef108152755258a4f5aa.png
[640_wx_fmt_jpeg 71]: https://img-blog.csdnimg.cn/img_convert/62c68c9e81848361ef3d2931131ee8fc.png
[640_wx_fmt_jpeg 72]: https://img-blog.csdnimg.cn/img_convert/5ffc2ea3584137c6d343d15e2164fea6.png
[640_wx_fmt_jpeg 73]: https://img-blog.csdnimg.cn/img_convert/586067d26d47747d34e7c21c6495bf5a.png
[640_wx_fmt_jpeg 74]: https://img-blog.csdnimg.cn/img_convert/6176239d631fa7dbf729b76790f9f522.png
[640_wx_fmt_jpeg 75]: https://img-blog.csdnimg.cn/img_convert/2559182a159a3c8703465935587e0938.png
[640_wx_fmt_jpeg 76]: https://img-blog.csdnimg.cn/img_convert/adb0a0e2595bb043542a7fcde6b84654.png
[640_wx_fmt_jpeg 77]: https://img-blog.csdnimg.cn/img_convert/d9a8b5535fd708113825ef9de5190062.png
[640_wx_fmt_jpeg 78]: https://img-blog.csdnimg.cn/img_convert/2be167a9c531dad5c39ccff65a9a2c65.png
[640_wx_fmt_jpeg 79]: https://img-blog.csdnimg.cn/img_convert/5b56ca6fe8b7107a9752254e7ec11be1.png
[640_wx_fmt_jpeg 80]: https://img-blog.csdnimg.cn/img_convert/4d100798ae2dd828271b15bd974cd4e4.png
[640_wx_fmt_jpeg 81]: https://img-blog.csdnimg.cn/img_convert/76ba08da58980e641d448dfb784e977c.png
[640_wx_fmt_jpeg 82]: https://img-blog.csdnimg.cn/img_convert/cc41a935647c61fcd1521ae8ab130a2d.png
[640_wx_fmt_jpeg 83]: https://img-blog.csdnimg.cn/img_convert/874d7594be31c7b273ef20c601783e01.png
[640_wx_fmt_jpeg 84]: https://img-blog.csdnimg.cn/img_convert/514f092807d8798ee0f85d6ee39fb2ff.png
[640_wx_fmt_jpeg 85]: https://img-blog.csdnimg.cn/img_convert/41a69ffb2ad391a6c2aed2d0d46011f6.png
[640_wx_fmt_jpeg 86]: https://img-blog.csdnimg.cn/img_convert/6f453f95579160e90140afef4253fd6e.png
[640_wx_fmt_jpeg 87]: https://img-blog.csdnimg.cn/img_convert/54c3e8659e19f6e2b83c4bbf2697baad.png
[640_wx_fmt_jpeg 88]: https://img-blog.csdnimg.cn/img_convert/01bd351be966bc1a8da24b979a5ed2a8.png