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

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

14
共 30 个回复

凭感觉写了个,多跑一遍似乎就好了,最短路径在每一行中,要么单调向左,要么单调向右。这是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;
    }
11

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


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

6

网络流?

2

对,是这样,原话的意思是,一行中的某个点,其最短路径要么由上一行往下一格得到,要么由左侧的点一直向右得到,要么由右侧的点一直向左得到,其实感觉像废话。

2

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

2

Dijkstra算法?

2

其实可以转换为单源最短路径问题,Dijkstra可解

1

需要遍历,纪录每一次遍历得到的和,之后的遍历,如果超过了之前的和,就跳出,如果小于,就重新记录。很快就可以得出结论了。实际写了一下,发现还是获取所有的路线比较难,遍历反而很简单。这是我的代码:

import sys
import time

sys.setrecursionlimit(9000000)  # 这里设置大一些


def list_list_get_min(list_0):
    end_list = get_step_list(list_0)
    print(end_list)
    sum_result = 0
    for func_x in end_list:
        sum_x = 0
        for index in func_x:
            sum_x += list_0[index[1]][index[0]]
        if sum_result == 0:
            print(func_x)
            print(sum_x)
            sum_result = sum_x
        if sum_x < sum_result:
            print(func_x)
            print(sum_x)
            sum_result = sum_x
    print(sum_result)
    return 0


def get_step_list(list_0, going_list=[], end_list=[]):
    # time.sleep(1)
    print('-'*30)
    print(going_list, end_list)
    if not list_0:
        return []
    # 如果还没开始
    if not going_list and not end_list:
        # 获取所有的起点坐标
        for i in range(len(list_0[0])):
            going_list.append([(i, 0)])
        return get_step_list(list_0, going_list, end_list)

    # 都走完了,返回结果
    if not going_list:
        return end_list

    # 如果已经开始,则递归获取所有的策略
    x0, y0 = going_list[0][-1]
    # 已经走完的,放进end_list
    if y0 == len(list_0) - 1:
        end_list.append(going_list[0])
        going_list = going_list[1::]
        return get_step_list(list_0, going_list, end_list)

    # 没走完的,获取下一步
    next_step = get_next_index(list_0, x0, y0)
    next_step = [i for i in next_step if i not in going_list[0]]
    # 把新生成的策略放进去
    for step in next_step:
        going_list.append([*going_list[0], step])
    # 上一步策略取出来
    going_list = going_list[1::]
    # 继续递归
    return get_step_list(list_0, going_list, end_list)


def get_next_index(list_0, x0, y0):
    next_step = []

    # 第一步只能前进
    if y0 == 0 and len(list_0) > 1:
        return [(x0, y0 + 1)]

    if x0 > 0:
        next_step.append((x0 - 1, y0))
        pass
    if x0 + 1 < len(list_0[0]):
        next_step.append((x0 + 1, y0))
    next_step.append((x0, y0 + 1))
    return next_step


a = [
    [7, 5, 1, 3],
    [1, 1, 1, 9],
    [1, 10, 3, 7],
    [1, 1, 1, 4],
    [2, 100, 1, 4]
]
# a = [
#     [10,2,1],
#     [10,2,100],
#     [1,2,1]
# ]
# next_step_list = get_next_index(a, 1, 2)
# print(next_step_list)
aaa = list_list_get_min(a)
1

双端dfs?

图像处理里的seam carving算法吧