时间戳

首页 > 解决方案 > 如何以小于指数的时间复杂度找到矩阵中从左上角到右下角的路径乘积？

c++ - 如何以小于指数的时间复杂度找到矩阵中从左上角到右下角的路径乘积？

问题描述

如果我们只能向右或向下移动，如何有效地找到从 mat[0][0] 到达 mat[r-1][c-1] 的路径乘积？1<= r，c <= 10^3。 例如，如果矩阵是 r=3，则 c=3。

1 2 3
4 5 6
7 8 9

一种可能的路径是 1->2->5->8->9 并且产品 = 1*2*5*8*9 = 720。

标签： c++algorithmmatrix

解决方案

MxN矩阵的路径数是

 / (M-1) + (N-1) \      / (M-1) + (N-1) \
|                 | =  |                 |
 \     M-1       /      \     N-1       /

对于可访问的论文，请查看致力于该问题的众多网络资源之一，例如。这个。

基本直觉是垂直和水平移动的数量在所有路径上都是固定的，因此可以将问题简化为计数排列。

对于NxN方阵，路径数是N第-个加泰罗尼亚数

       / 2 N \     / 2 N \
C_N = |       | - |       |
       \  N  /     \ N+1 /

（参见例如维基百科文章）。

无论如何，这意味着产品的数量是指数级的N，因此效率将受到限制。

如果您对根据某些标准的最佳路径感兴趣，则该问题可能允许动态规划，从而允许多项式空间和时间。

推荐阅读