同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

如何编程获得最多的年终红包奖？

2022-5-16 18:47| 发布者: Hocassian| 查看: 81| 评论: 0|原作者: 五分钟学算法微信公众号

摘要:

如何编程获得最多的年终红包奖？

五分钟学算法

文章转载自公众号

互联网侦察，作者 channingbreeze

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

加个“星标”，一起学算法

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

    }
}