为什么组数和步数要反过来动规?

P1130 红牌

恶心的输入
by caohan @ 2023-05-23 18:10:28


理论上来讲,不存在前i组完成前j步的最少使用天数,因为第一组的最少时间和最后一组挂钩,最后一组的时间又和倒数第二组挂钩。 dp需要满足最优子结构,如果从上到下遍历的话是不符合最优子结构的,因为后求出的值可能会影响前面的值,比如第一行第i个数会被第m行第i-1个数影响,从而先前求出的解就不一定是最优解,自然不能从上到下dp。 另外,我不太理解代码中三个循环的作用,但是我估计你的问题和我上面说的一样,~~问就是我第一反应也这样~~。
by Fecser_617 @ 2023-06-23 10:01:14


|