动态规划要求其子问题既要独立又要重叠,这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的,但它们描述了两种不同的概念,而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源,则它们就是独立的。对两个子问题来说,如果它们确实是相同的子问题,只是作为不同问题的子问题出现的话,是重叠的,则它们是重叠。
有一座独木桥,长度为L,青蛙每跳一次的最大距离为M,最小距离为S,桥上有N个石墩,石墩不会落在两端只在桥中间,桥墩位置数组为Postions,青蛙很不喜欢站在石墩上。问:青蛙最少要几步能过桥,而且满足落在石墩上的次数最少。举例输入:L=10,S=1,M=3,N=5,Positions=[2,4,5,7,9] 应该输出:2