动态规划-跳跃式千斤顶

Question

有人可以帮助解决以下问题，使用DP技术。

不需要代码。这个想法应该足够了。

惊奇漫画即将推出一个新的超级英雄，名为跳跃杰克。这位超级英雄的共同创造者是一位数学家，他为角色的力量添加了数学元素。

所以，跳跃杰克最突出的能力之一是跳跃距离。但是，这个超级大国有一定的限制。

杰克只能跳-

1. 到比当前距离小一公里的数字。例如，如果他离目的地12公里，他就不能直接跳到目的地，因为他只能跳到11公里外的地方。
2. 到当前距离的一半的距离。例如，如果Jumping Jack距离目的地12公里，他将无法直接跳到目的地，因为他只能跳到6公里外的位置。
3. 到一个距离，它是当前距离。例如，如果Jumping Jack距离目的地12公里，他将无法直接跳到目的地，因为他只能跳到4公里外的位置。

因此，您需要帮助超级英雄开发一种html" target="_blank">算法，以最少的步骤到达目的地。目的地定义为距离变为1的位置。跳跃千斤顶应能跑完最后1公里！此外，他只能跳到距离主目的地整数距离的目的地。例如，如果他在10公里处，通过跳1/3的距离，他无法达到10/3的距离。他要么跳到5，要么跳到9。

因此，您必须找到到达目的地所需的最小跳跃次数。例如，如果目的地在10公里之外，有两种方式可以到达：10-

Answer 1

考虑f（1）＝0，因为当JumpingJack在1公里之外时所需的跳跃数是没有的。使用此基值解F[2]。。。f[n]以下面的方式

        for(int i=2; i<=n; i++) {
            if(i%2==0 && i%3==0) {
                f[i] = Math.min(Math.min(f[i-1]+1, f[i/2]+1), f[i/3] + 1);
            }
            if(i%2==0) {
                f[i] = Math.min(f[i-1]+1, f[i/2]+1);
            }else if(i%3==0) {
                f[i] = Math.min(f[i-1]+1, f[i/3] + 1);
            }else{
                f[i] = f[i-1]+1;
            }
        }
        return f[n];

您不需要多次递归地解决子问题！

Answer 2

首先，思考一下这个换硬币的问题可能会帮助你理解你的问题，它们几乎是一样的：换硬币-DP

其次，通常如果你知道你的问题有一个DP解决方案，你可以做4个步骤来解决它。当然，您可以执行前3个步骤中的一个或所有步骤。

>

找到回溯解决方案。（此处省略）

根据回溯解决方案，找到问题的递归公式。（稍后描述）

根据递归公式编写递归代码。（省略）

最后，对于你的问题，公式不难理解：

minStepFor(distance_N)=Math.min(minStepFor(distance_N-1)+1),
                                minStepFor(distance_N/2)+1, 
                                minStepFor(distance_N/3)+1)

试想一下jack站在距离N点，他第一次去最多有三个选项：去N-1点，或者N/2点，或者N/3点（如果N/2或N/3不是整数，他的选择会减少）。

对于他的每一个选择，最小步数是minStepFor（left distance）1，因为他已经走了1步，他肯定会尝试在他的向左移动中走最小步数。并且每个选项的左侧距离是距离N-1，距离N/2和距离N/3。

这就是理解公式的方法。使用它编写递归解决方案并不困难。

Answer 3

解决所有动态规划问题时，应牢记以下两点：

• 最优子结构（求最小跳跃次数）
• 重叠子问题（如果你再次遇到相同的子问题，不要解决它，而是使用已经计算的结果——是的，你必须存储子问题的计算结果以备将来参考）

始终尝试为手头的问题制定递归解决方案（现在不要直接看递归解决方案，而是首先自己尝试）：

calCulateMinJumps(int currentDistance) {
    if(currentDistance == 1) {
        // return jumps - you don't need to recurse here
    } else {
        // find at what all places you can jump
        jumps1 = calculateMinJumps(n-1) + 1
        if(currentDistance % 2 == 0)
            jumps2 = calculateMinJumps(n/2) + 1
        if(currentDistance % 3 == 0)
            jumps3 = calculateMinJumps(n/3) + 1
        return minimum(jumps1, jumps2, jumps3) // takes jump2 and jump3 only if they are valid
    }
}

现在你知道了，我们已经设计了一个递归解决方案。下一步是将解决方案存储在一个数组中，以便将来可以使用它并避免重新计算。您可以简单地获取一个1-D整数数组并继续存储它。

请记住，如果你采用自上而下的方法——它将被称为记忆化，如果你采用自下而上的方法——它将被称为动态编程。看看这个，看看这两种方法的确切区别。

一旦你有了一个递归解决方案，你现在可以考虑构建一个自下而上的解决方案，或者自上而下的解决方案。

在自下而上的解决方案策略中-您首先填写基本情况（跳跃式千斤顶应覆盖最后1公里的跑步距离！），然后在此基础上进行构建，以获得最终所需的解决方案。

现在，我不会给你们完整的战略，因为这将是你们要完成的任务。你会找到解决办法的按照您的要求，想法应该足够了。