081. 路径数字之和:两个方向(Path sum: two ways)

在下面的五乘五的矩阵中,从左上角到右下角并且每次只能向右和向下移动的的最小的路径之和是2427,路径正如图中红字所标示:

$$ \begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix} $$
在附件 matrix.txt中有一个八十乘八十的的矩阵,求这个矩阵的从左上角到右下角且每次只能向右或向下移动的最小路径和。

分析:这是一道典型的动态规划例题,我们之前已经碰到过多次,如第十五题目、第十八题和第六十七题,我们只需要使用同样的动态规划思路求解即可。观察图中已经给出的矩阵,要求从左上角到右下角,也就是从131到331的最小路径和。因为题目要求只能向右或向下移动,则到达331只有两种方法,一种是从956向下移动一格,一种是从37向右移动一格,则到达331的最小路径和应该是到达956的最小路径和以及到达37的最小路径和中的最小值再加上331,到达矩阵中其它元素的最小路径和也是一样的。

此外,如果某个元素位于矩阵的第零行,则只能从左这一方向到达该元素(因为不能向上移动),则到达该元素的最小路径和即该行第一个元素到该元素的所有元素之和。同理,如果某个元素位于第零列,则到达该元素的最小路径和为该列第一个元素到该元素的所有元素之和。最后,如果该元素位于第零行,第零列,则到达该元素的最小路径和为该元素本身。因此,设某个元素位于矩阵\(M\)的第\(r\)行,第\(c\)列,到达该元素的最小路径和为\(mps(r,c)\),则该动态规划问题的状态转移方程可以表述为:

img

代码如下:

# time cost = 8.01 ms

from functools import lru_cache

with open('data/ep81.txt') as f:
    table = [list(map(int,s.split(','))) for s in f.readlines()]

@lru_cache(maxsize=2048)
def min_path_sum(r,c):
    if r == 0 and c == 0:
        return table[0][0]
    elif r == 0 and c >= 1:
        return sum(table[r][:c+1])
    elif c == 0 and r >= 1:
        return sum(x[0] for x in table[:r+1])
    else:
        return table[r][c] + min(min_path_sum(r-1,c),min_path_sum(r,c-1))  

def main(N=80):
    return min_path_sum(N-1,N-1)