我被这个作业问题难住了。我想我有正确的答案，但不确定如何证明。我也不确定如何处理证明。这是问题所在:
Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations.
The professor’s goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time.
我认为他应该选择停靠点，以便在水用完之前走最远的距离。也就是说，在每一站，如果他继续前进，他会在下一站之前耗尽水。
我不确定如何进行。我敢打赌以前有人这样做过，但我对 CS 领域还很陌生，需要一些指导。
最佳答案
你的算法是正确的。
尝试通过对经过的停靠点数进行归纳来证明以下内容。 经过每个水域位置后，没有其他策略可以减少停留次数，而在停止次数相同的策略中，没有其他策略可以让您留下更多的水。
在 0 站所有策略都是平等的，因此证明该陈述是微不足道的。
如果你在这个策略下一站不喝酒，结果很容易证明。
如果你确实在一站喝酒，从上一站的陈述是正确的事实，你可以证明其他策略上次做了更多的停止(因此他们在停止时没有领先，也不能因为你刚有水，所以在水上领先)，否则其他策略也必须同样有水(否则他们会在下一站之前用完水)。
这足以填写归纳证明。
如果您对正式证明所需的概念以及如何进行证明感到困惑，请参阅 How I Do Proofs .我还在博客上写了我使用该讲义的经历 here .
关于algorithm - 带有扭曲的图形遍历算法 - 最小停止次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6221600/