是经典的老鼠进洞问题!
下面两张图,第一个的题面是“n 只老鼠,m 个能容纳一只老鼠的洞,老鼠只能往左走,问全部进洞的最小距离和”,第二个是把老鼠只能往左走去掉。
(我推测那个“−xi 单调递减”应该写成“−yi 单调递减”)
我的问题就出在第二张图的 yi,它是单调递增的,此时为什么还是一定比 f[i−1][j] 优。。
比如洞所在的位置为 1,7,8,⋯,老鼠所在的位置为 3,5,6,⋯ 时,f[8][−1] 就应该从 f[7][−1] 转移,而不是从 f[7][−2]+8 转移吧/kel