gpt4 book ai didi

algorithm - 在元素总和为目标数的矩阵中高效地找到一条路径?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:36:40 24 4
gpt4 key购买 nike

<分区>

编程问题

输入: m x n 严格正数矩阵,目标数 T。

输出: 一条从入口 (0,0) 开始到最后一行结束的简单路径。我们只能在任何给定步骤向右或向下移动。此外,路径元素的总和必须恰好为 T。没有其他限制。

我已经实现了一个正确的蛮力解决方案,但我们谈论的是指数时间。是否存在更有效的解决方案(可能使用动态规划)?

我看到一个类似的现有问题,但答案有限,有人声称这个问题是 NP-Complete,但我无法验证这一点: Finding a path whose elements sum up to a given number in a matrix

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com