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