本文共 266 字，大约阅读时间需要 1 分钟。

原文链接：

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的值。

转载地址：https://www.cnblogs.com/Friends-A/p/11054979.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！