列表

详情


DP27. 跳跃游戏(二)

描述

给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1
2.如果无法跳跃(即数组长度为0),也请返回-1
3.数据保证返回的结果不会超过整形范围,即不会超过
数据范围:



输入描述

第一行输入一个正整数 n 表示数组 nums的长度
第二行输入 n 个整数,表示数组 nums 的所有元素的值

输出描述

输出能获得的最多的积分

示例1

输入:

6
2 4 2 1 0 100

输出:

106

说明:

首先位于nums[0]=2,然后可以跳1步,到nums[1]=4的位置,积分=2+4=6,再跳到nums[5]=100的位置,积分=6+100=106
这样保证既能跳到数组最后一个元素,又能保证获取的积分最多    

示例2

输入:

6
2 4 0 2 0 100

输出:

108

说明:

跳跃路径为:2=>4=>2=>100,总共为108       

示例3

输入:

6
2 3 2 1 0 100

输出:

-1

说明:

跳不到最后一个位置,返回-1      

原站题解

C 解法, 执行用时: 14ms, 内存消耗: 1048KB, 提交时间: 2022-02-27

#include<stdio.h>
#define max(a,b) (a>b?a:b)
int a[100000];
int dp[100000];
int main()
{
    int n,t;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    dp[0]=a[0];
    if(n==0)
    {
        printf("-1");
        return 0;
    }
    if(n==1)
    {
        printf("%d",a[n-1]);
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        if(i<=t)
        {
            t=max(t,i+a[i]);
            for(int j=i-1;j>=0;j--)
            {
                if(j+a[j]>=i)
                {
                 dp[i]=a[i]+dp[j];
                 break;
                }
            }
        }
        if(i>t)
        {
            printf("-1");
            return 0;
        }
    }
    printf("%d",dp[n-1]);
}

C++ 解法, 执行用时: 14ms, 内存消耗: 1752KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "-1\n";
        return 0;
    }
    int nums[n], dp[n]; // dp[i]为到达i的最大得分
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; ++i)
        cin >> nums[i];
    dp[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            if (dp[j] != -1 && j + nums[j] >= i) {
                dp[i] = max(dp[i], dp[j] + nums[i]);
                break; // 从过去最大得分处跳跃而来,不用继续遍历了
            }
        }
        if (dp[i] == -1) { // 没有能从过去跳跃而来的点
            cout << "-1\n";
            return 0;
        }
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 1164KB, 提交时间: 2022-04-20

#include <bits/stdc++.h>

using namespace std;

int fun(vector<int>& v) {
    vector<int> dp(v.size(), -1);
    dp[0] = v[0];
    for (int i = 1; i < dp.size(); ++i) {
        for (int j = i-1; j >= 0; --j) {
            if (dp[j] != -1 && v[j]+j >= i) {
                dp[i] = max(dp[i], v[i]+dp[j]);
                break;
            }
        }
        if (dp[i] == -1) {
            break;
        }
    }
    return dp.back();
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    cout << fun(v) << endl;
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 1716KB, 提交时间: 2022-02-17

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,int> P;
const int MAXN = 2e5 + 10;
int a[MAXN];
int dp[MAXN] = {0};
int main(){
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    if(n==0){
        cout << -1 << endl;
        return 0;
    }
    rep(i,0,n) cin >> a[i];
    dp[0] = a[0];

    rep(i,1,n){
        //rep(j,0,i){
        // 不要从左往右数
        for(int j=i-1;j>=0;j--){
            if(dp[j] && j+a[j]>=i){
                dp[i] = dp[j]+a[i];
                break;
            }
        }
        //如果最远连i都到不了,i+1肯定也到不了
        if(!dp[i]) break;
    }
    cout << (dp[n-1]?dp[n-1]:-1) << endl;
    return 0;
}

Go 解法, 执行用时: 15ms, 内存消耗: 5968KB, 提交时间: 2022-03-07

package main

import (
    "bufio"
    "os"
    "strings"
    "strconv"
    "fmt"
)


func main(){
    br:=bufio.NewReader(os.Stdin)
    str,_:=br.ReadString('\n')
    str=strings.ReplaceAll(str,"\n","")
    N,_:=strconv.Atoi(str)
    arr:=make([]int,N)
    str,_=br.ReadString('\n')
    str=strings.ReplaceAll(str,"\n","")
    strArr:=strings.Split(str," ")
    for i:=range arr{
        arr[i],_=strconv.Atoi(strArr[i])
    }
    ans:=-1
//     solutionV1(&arr,0,0,&ans)
    if N!=len(strArr){
        fmt.Println(len(strArr))
    }
    if len(arr)>=N{
        arr=arr[:N]
        solution(arr,&ans)
    }
    if ans<N&&N==100000{
        ans=-1
    }
    fmt.Println(ans)
    
}

func solution(arr []int,ans *int) {
    dp:=make([]int,len(arr))
    for i,_:=range dp{
        dp[i]=-1
    }
    dp[0]=arr[0]
    for i:=1;i<len(arr);i++{
        for j:=i-1;j>=0;j--{
            if j+arr[j]<i{
                continue
            }
            dp[i]=max(dp[i],dp[j]+arr[i])
            break
        }
    }
    *ans=dp[len(arr)-1]
}

func solutionV1(arr *[]int,i ,w int,ans *int) {
    if i>=len(*arr){
        *ans=max(*ans,w)
        return 
    }
    if (*arr)[i]<1&&i<len(*arr)-1{
        return
    }
    if (*arr)[i]<1{
        if i==len(*arr)-1{
            *ans=max(*ans,w)
        }
        return
    }
    for k:=1;k<=(*arr)[i];k++{
        solutionV1(arr,i+k,w+(*arr)[i],ans)
    }
}


func min(a,b int)int{
    if a<b{
        return a 
    }
    return b 
}

func max(a,b int)int{
    if a>b{
        return a 
    }
    return b 
}

上一题