mod4最優路徑問題

如下圖：

??

從1到4找出一條路徑，要求路徑的總長度mod4的余數最小。

分析：一條從1到4的最優路徑，在它走到2或3時mod4的余數不一定最小。也就是說，最優策略的子策略不一定最優，所以本問題不滿足最優化原理，那么也就不能用動態規劃來解決。但是我們可以把它轉化為判定性問題，用遞推來解決。

設dp[k][i]為bool型數組，表示從1點到k點長度mod4為i的路徑是否存在，設len[k][i]表示從第k-1到第k點之間的第i條邊的長度。那么就有

? ?

顯然邊界條件是：

? ??

那么結果就是使為真的最小的i的值。

總結

以上是生活随笔為你收集整理的mod4最优路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。