到达终点的最小跳跃

Question

问题声明：给定数组：[1,0,1,0,1,1,1,1,1,0,1,1,1,0]输出：到达结束所需的最小步骤

条件：

• 0上的步骤是退出

我已经完成了不使用DP的情况下的使用，是否存在针对此问题的DP解决方案。

我的代码：

def minjump(arr):
    n = len(arr)
    if n <= 0 or arr[0] == 0:
        return 0

    index = jump = 0
    while index < n:
        if index == n-1:
            return jump

        if arr[index] == 0 and arr[index+1] == 0:
            return 0

        if arr[index] == 1:
            if index < n-2 and arr[index+2] == 1:
                jump +=1
                index +=2
            else:
                jump += 1
                index += 1
    return jump

Answer 1

您可以使用dp解决更一般的问题，在伪代码中，下面的k表示您可以跳转的最大步数：

int n = arr.Length
int dp[n]
for (i = 0 ; i < n; i++) {
    int lowerBound = max(i - k, 0)
    for (j = i - 1; j >= lowerBound; j--) {
        if (arr[j] == 1 && (j == 0 || dp[j] > 0)) {
            dp[i] = min(dp[i], 1 + dp[j])
        }
    }
}
return dp[n - 1]

Answer 2

一个没有记忆的天真解决方案只是在列表中反复出现，采取一个或两个步骤，并保留所需的最小步骤：

def min_steps(array, current_count, current_position):
   if current_position >= len(array):  # Terminal condition if you've reached the end
       return current_count
   return (
       min(
           min_steps(array, current_count + 1, current_position + 1),
           min_steps(array, current_count + 1, current_position + 2),
       )  # minimum count after taking one step or two
       if array[current_position]  # if current step is valid (non-zero)
       else float("inf")  # else, return float.infinity (fine since we're not imposing types on this prototype)
   )


def minjump(arr):
   result = min_steps(arr, 0, 0)
   return 0 if result == float("inf") else result