讨论/面试考题/之前阿里实习笔试遇到一道题,想讨论一下解题思路/
之前阿里实习笔试遇到一道题,想讨论一下解题思路

之前在面试阿里实习的时候遇到了一道题没有能做出来,虽然感觉也没有特别难,但是仍然苦于没有思路,故想和大家讨论一下。
大概意思就是给定一个mXn的矩阵,矩阵里面都是非负整数,那么现在要从蓝色区域出发(矩阵上边的矩阵外的区域),要到达红色区域,请问这个过程中的路径和最小是多少?
你可以从第一行任意一个起点出发,行走的时候可以 往下走,往左走,往右走。求最小的路径和。
如果有思路的大家可以一起讨论呀~
(忘了加个条件,矩阵里都是非负数)
image.png

展开讨论
tommy发起于 2020-07-17
最近编辑于 2020-07-17
共 10 个讨论

凭感觉写了个,多跑一遍似乎就好了,最短路径在每一行中,要么单调向左,要么单调向右。这是dp的结果:
[7, 5, 1, 3],
[6, 3, 2, 11],
[6, 4, 5, 12],
[7, 5, 15, 16]
往上走也差不多,问题怎么把对应的状态统计进去,大概。但如果有负数,或者能同时上下左右的话,好像会变得非常麻烦。
代码如下,如有问题请指出。

public int minPath(int[][] matrix) {
        // 输入校验
        if (matrix == null || matrix.length == 0)
            return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        // 取第一行
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i];
        }
        // dp
        for (int i = 1; i < m; i++) {
            // 先从左至右跑一遍
            for (int j = 0; j < n; j++) {
                dp[i][j] = matrix[i][j] + (j == 0 ? dp[i - 1][0] : Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
            // 再从右至左跑一遍
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = j == n - 1 ? dp[i][j] : Math.min(dp[i][j], matrix[i][j] + dp[i][j + 1]);
            }
            // 最后一行就结束了,直接取上一行结果+matrix[i][j]应该就好了,但是边界判断有些繁琐
        }
        int res = Integer.MAX_VALUE;// 返回值
        // 跑一遍最后一行,拿到最短路径和
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[m - 1][i]);
        }
        return res;
    }
6

没有负数的话直接 dp 就行了


https://projecteuler.net/problem=82 原题

2

标准动态规范
可以分成两个动态规划表,一个只向左下遍历,一个只向右下遍历,最后求两者的最小值就好

1

这不是标准的dp么

Dijkstra算法?

有道题是说从左上角走到右下角的,求方式数,你这个和那个是一样的,把所有的起点都加起来就行了

标准DP😃

image.png
这种情况咋搞 (0.0)

这问题跟120 三角形的最小路径和问题类似你可以看看那个题

我是这样想,为什么前面要拐呢?第一行不用拐,因为如果需要更小的值,替换为从那一个开始就可以了;同理最后一行不用拐。然后我们开始求直竖线的dp,正常情况走直线最短,除非走到上一行的某一列,再拐过来可以求得更小的值,才替换当前累计的dp值。因为左右都可以拐,所以计算时需要一行的缓存保证数据不会脏。算好一行赋值。