java - 最大限度地提高您在通过阵列时获得的金额

Question

例如，给定一个整数数组， [1 4 3 2 9 8 7 6] 每个整数代表你可以捡到的钱数。你在阵中穿梭，可以捡到钱。每次你捡到一些钱，你必须再旅行 X 量 (minInterval) 才能捡到更多的钱。- 那就是你必须等待 X 次旅行才能拿到更多的钱。给定 minInterval，您最多可以拿到多少钱。

注意：每次旅行本质上只是移动到下一个索引。你想最大化你捡到的钱的价值。

例如，如果最小间隔为 4，则最佳路径将是，

什么是完成此任务的好算法？这基本上是一个优化问题。

Answer 1

您可以使用动态规划来解决问题。从最后一个元素到第一个元素遍历数组，那么每个元素都有两个选择：

1.选择当前元素，从第i+x个元素过渡dp[i]=dp[i+x]+a[i]

2.不选择当前元素，transit from dp[i+1]，表示可以从interval得到的最大值[i+1,n]

那么你可以得到：dp[i]=max(dp[i+1],dp[i+x]+a[i])

所以：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n,x;

    cin>>n>>x;
    vector<int> a(n+1);
    vector<int> dp(n+1+x);

    for(int i=1;i<=n;++i) cin>>a[i];

    for(int i=n;i>=1;--i){
        dp[i]=max(dp[i+1],dp[i+x]+a[i]);
    }

    cout<<dp[1]<<endl;

    return 0;
}