到达终点的最小跳跃

Question

问题陈述：给定数组：[1,0,1,0,1,1,1,1,1,0,1,1,1,0] 输出：到达终点所需的最少步数

条件：

踩到0就是退出
您一次最多可以走 1 步或 2 步。

我已经在没有 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

到达终点的最小跳跃

minimum jump to reach to end

python

algorithm

dynamic-programming