1.dp數組有關元素--路長和次數

2.遞推公式

3.遍歷順序--最終影響的是路長，在外面

其次次數遍歷，即這次路長所有情況都更新

最后，遍歷次數自然就要遍歷跳長

4.max時時更新

dp版本

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n,a,b,k,t;
ll w[110];
ll dp[110][110];
ll ma;
ll s;	
int main() {cin>>t;while(t--){memset(dp,0,sizeof(dp));ma=0; cin>>n>>a>>b>>k;for(int i=1;i<=n;i++) cin>>w[i];dp[0][0]=0;for(int i=1;i<=min(n,k*b);i++)///路長為i {for(int j=1;j<=k;j++)///跳了j次 {for(int l=a;l<=b;l++)///上一次跳了l，即上次是路長i-l {if(i-l>=0){if(dp[i-l][j-1]==0)///dp==0說明沒跳到，不能轉移 {if(i==l&&j==1)///特例，就是dp[0][0] dp[i][j]=max(dp[i][j],dp[i-l][j-1]+w[i]);}else dp[i][j]=max(dp[i][j],dp[i-l][j-1]+w[i]);ma=max(ma,dp[i][j]);///記錄max }}}	}cout<<ma<<endl;}return 0;
}

2.記憶化版本--YYDS！

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n,a,b,k,t;
ll w[110];
ll dp[110][110];
ll ma;
ll s;
ll dfs(int l,int x)
{
if(l>n||x<0) return  0;///越界return 0 
ll ma=0;
if(dp[l][x]!=-1) return dp[l][x];///記憶化剪枝 
if(x==0)///沒有次數就是沒有未來，return 0 
{return 0;
}
for(int i=a;i<=b;i++)
{	if(l+i<=n){ma=max(ma,dfs(l+i,x-1)+w[l+i]);///當前路長當前次數的ma }
}
return dp[l][x]=ma;///計的就算l長x次的極致MAX！ 
} 
int main() {cin>>t;while(t--){cin>>n>>a>>b>>k;memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++) cin>>w[i];dfs(0,k);cout<<dp[0][k]<<endl;}return 0;
}