跳跃游戏二,拾起我的算法!

来源:计蒜客_t20

给定一个非负整数数组,假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

你的目标是到达最后一个下标,并且使用最少的跳跃次数。

例如:

A = [2,3,1,1,4], 到达最后一个下标的最少跳跃次数为2.(先跳跃1步,从下标0到1,然后跳跃3步,到达最后一个下标。一共两次)

格式:

第一行输入一个正整数n,接下来的一行,输入数组A[n]。

最后输出最少的跳跃次数。

样例1

输入:

5
3 1 1 1 1

输出:

2

分析:

 初看这道题感觉一道二维动态规划问题,那么解这道题的核心就是如何构造动态规划数组。由于我好长时间没碰过动态规划了,一时竟然想不起来思路,于是又默默滚回去复习了背包问题,回来再看,还是不会 (ノಠ益ಠ)ノ彡┻━┻。仔细分析了一下动态规划的基本算法,总结出来一点规律,希望对读者有所帮助。

 首先来说01背包问题,题目不再描述,这道题总共有三个『变量』,分别是物体,体积和价值。最终目的是价值最大。所以这道题构造了一个这样的动态规划数组:

f[i][j]=k,表示前i件物品恰放入一个容量为v的背包可以获得的最大价值为k

从而很容易得到递推公式为:

f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+w[i])

 相信看到这里,你已经隐约猜到了一些什么。没错!题目中的三个『变量』前两个是动态规划数组的行和列,最后一个要求的最大/最小值是数组中存的值!!!
 再看这道题,很容易能找到两个『变量』位置和跳跃次数,最后一个可能一看不出来,但是仔细分析就会发现题目中已经没有更多的变量了,只剩一个就是:跳跃距离。

 所以我们参照背包问题的思路构造如下的数组:

dp[i][j] = k, 表示当前位置为i,且上一次跳跃距离为j时的最小次数为k

现在很容易就可以得到如下递推公式:

dp[i][j] = min{dp[i-j][l]} (0<=l<n) //注意要考虑不能到达的情况

接下来问题就是敲代码了。

/*
name: jisuanke_T20 - jump game
author: yichin
algorithm: dynamic programing
*/
#include <iostream>
#include <cstdio>
#include <cstring>

#define MaxN 1005

using namespace std;

int dp[MaxN][MaxN];

int main()
{
    int n = 0;
    int A[MaxN] = {0};
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        scanf("%d", &A[i]);
    }
    //dynamic programing
    //dp[i][j] = k means on location i with the last jump distance j, the times of jump is k
    //dp[i][j] = min(dp[i-j][k]) k=[0,n]

    //initialize array
    int min_times[MaxN];
    memset(min_times, -1, sizeof(min_times));
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    min_times[0] = 0;

    for(int i=1; i<n; ++i){
        for(int j=1; j<=i; ++j){ dp[i][j] = ((min_times[i-j] > -1) && (A[i-j] >= j)) ? min_times[i-j] + 1 : -1;
            if(min_times[i] < 0){ min_times[i] = dp[i][j]; }else if(dp[i][j] > -1 && dp[i][j] < min_times[i]){
                min_times[i] = dp[i][j];
            }
        }
    }
    printf("%d\n", min_times[n-1]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注