网址：http://www.bubuko.com/infodetail-7972.html 如下图：
从1到4找出一条路径，要求路径的总长度mod4的余数最小。
分析：一条从1到4的最优路径，在它走到2或3时mod4的余数不一定最小。也就是说，最优策略的子策略不一定最优，所以本问题不满足最优化原理，那么也就不能用动态规划来解决。但是我们可以把它转化为判定性问题，用递推来解决。
设dp[k][i]为bool型数组，表示从1点到k点长度mod4为i的路径是否存在，设len[k][i]表示从第k-1到第k点之间的第i条边的长度。那么就有
显然边界条件是： 那么结果就是使为真的最小的i的值。 上面的动态规划方程是有问题的。因为i-len[k][1]可能为负数，数组可能越界。 应该是：
为真的最小的i的值。{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 sleedr 的文章《模4 最优路径问题》','https://www.xiaopingtou.net/article-52330.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
。为什么会是dp[k-1][ (sk-len[k][i]) % 4] 这个表达式呢。 其实sk=(s(k-1) +len[k][i] )%4; 所以通过sk去求s(k-1)的时候 s(k-1) + len[k][i] =sk + 4*E (E为整数 0 或1) 所以 s(k-1) =( sk +4 *E - len[k][i])% 4