如何從某個位置查找所有可能的可到達號碼？

由於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（含）之間。如何從某個位置查找所有可能的可到達號碼？

重要提示：如果在操作過程中，我們得到一個值s < 1或S> N，我們不帶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 <相同的情況）。

來源

2016-05-14 Godfather

燦你確認你已經以正確的方式提及了'm'和'n'，並且有時候沒有使用錯誤的引用？看起來你在某個時候混淆了它們。 – trincot

我提到他們的權利，告訴我你在哪裏混亂？ – Godfather

令我困惑的是數組的大小是'm'，但絕不允許你訪問'n'上的元素。所以如果'n m'，那麼如何處理's = n'，因爲可能沒有'n-1'的數組元素？另外，我不明白'A'是從哪裏來的。 – trincot

有此動態規劃的解決方案，它運行在O(nm)時間，需要O(n)空間。

首先建立一個名爲reachable的布爾數組，將其初始化爲false，除了reachable[s]，即true。

此數組現在表示在0步驟中是否可以訪問數字。現在對每一個i從1到m，我們更新了數組，這樣reachable[x]代表數字x是否i步可達。這很容易：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]])

這裏last_r[x]是按照慣例false如果x不在範圍[1 .. n]。

如果你想保持的每個數字可以達到的方式號碼，然後你做了以下變化：

改變數組r整數數組;
在初始化時，初始化所有的r[x]到0，除了r[s]到1;
在主循環中，更改鍵行：

- [R [X] = last_r [X + A [K]] + last_r [X - A [K]]

來源

2016-05-14 18:01:19 WhatsUp

可否請你提供一個簡單的僞代碼，我有點困惑 – Godfather

這個代碼是否也跟蹤一個值的計數，就像上面的例子2發生了兩次。 – Godfather

@Godfather看我的編輯。這只是一個小小的修改，一旦你明白它是如何工作的。 – WhatsUp

如何從某個位置查找所有可能的可到達號碼？

回答

相關問題