最大化你在穿过阵列时捡到的钱

Question

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

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

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

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

Answer 1

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

1.choose当前元素，从第i+x个元素开始dp[i]=dp[i+x]+a[i]

2.don不选择当前元素，从dp[i+1]过渡，表示区间[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;
}

最大化你在穿过阵列时捡到的钱

Maximize the amount of money you pick up as you travel through an array

java

algorithm

optimization

knapsack-problem

maximization