algorithm - 如何从一个位置找到所有可能可达的数字？

Question

给定2 elements n, s and an array A of size m , 其中s is initial position位于 1 <= s <= n 之间，我们的任务是对 s 执行 m 操作，并且在每个操作中我们要么使 s = s + A[i] 要么 s = s - A[i]，并且我们必须打印 m 操作后可能的所有值所有这些值应介于 1 - n(含)之间。

Important Note: If during an operation we get a value s < 1 or s > n, we don't go further with that value of s.

我使用 BFS 解决了这个问题，但问题是 BFS 方法在这里不是最优的，有人可以向我建议任何其他更优化的方法或者算法会很有帮助。

例如:-

如果 n = 3，s = 3，且 A = {1, 1, 1}

                            3
                         /     \
operation 1:           2         4  (we don’t proceed with 4 as it is > n)
                   /   \         /  \
operation 2:     1       3      3    5
                / \     / \    / \   / \
operation 3:   0   2   2   4  2   4  4  6

因此，遵循上述规则可达到的最终值为 2 和 2(即 2 的两倍)。我们不考虑第三个两个，因为它有一个 > n 的中间状态(如果 < 1，则适用相同的情况)。

Answer 1

有这个动态规划解决方案，运行时间为O(nm)，需要O(n)空间。

首先建立一个名为reachable的 bool 数组，除了reachable[s]为true外，其他地方都初始化为false 。

这个数组现在表示一个数字是否可以在 0 步内到达。现在对于从 1 到 m 的每个 i，我们更新数组以便 reachable[x] 表示是否数字 x 可在 i 步内到达。这很简单:当且仅当 x - A[i] 或 x + A[ i] 可在 i - 1 步内到达。

最后数组就变成了你想要的最终结果。

---

编辑:这里是伪代码。

// initialization:
for x = 1 to n:
    r[x] = false
r[s] = true

// main loop:
for k = 1 to m:
    for x = 1 to n:
        last_r[x] = r[x]
    for x = 1 to n:
        r[x] = (last_r[x + A[k]] or last_r[x - A[k]])

如果 x 不在 [1 .. n].

如果您想维护每个数字的到达方式数量，那么您可以进行以下更改:

1. 将数组r改为整型数组；
2. 在初始化中，将所有r[x]初始化为0，除了r[s]为1 >;

3. 在主循环中，将关键行更改为:

   r[x] = last_r[x + A[k]] + last_r[x - A[k]]