問題描述
　　有一條長為n的走廊，小明站在走廊的一端，每次可以跳過不超過p格，每格都有一個(gè)權(quán)值wi。
　　小明要從一端跳到另一端，不能回跳，正好跳t次，請問他跳過的方格的權(quán)值和最大是多少？
輸入格式
　　輸入的第一行包含兩個(gè)整數(shù)n, p, t，表示走廊的長度，小明每次跳躍的最長距離和小明跳的次數(shù)。
　　接下來n個(gè)整數(shù)，表示走廊每個(gè)位置的權(quán)值。
輸出格式
　　輸出一個(gè)整數(shù)。表示小明跳過的方格的權(quán)值和的最大值。
樣例輸入
8 5 3
3 4 -1 -100 1 8 7 6
樣例輸出
12
數(shù)據(jù)規(guī)模和約定
　　1<=n, p, t<=1000, -1000<=wi<=1000
思路：挺基礎(chǔ)的一個(gè)dp,dp[i][j]代表著在第i個(gè)格子跳j次最大值，最后輸出的是dp[0][t]。
初始化的時(shí)候，是初始化的后p個(gè)格子，因?yàn)樗鼈兲淮尉涂梢缘阶詈?#xff0c;那么dp[n-p+1~p][1]就是已知的。
一個(gè)坑點(diǎn):p有可能大于n，這里需要注意，否則會運(yùn)行出錯(cuò)。
代碼如下（記憶化搜索）：

#include<bits/stdc++.h> #define ll long long #define inf 1e9 using namespace std;const int maxx=1e3+100; int a[maxx]; ll dp[maxx][maxx]; int n,p,t;inline ll dfs(int u,int num) {if(dp[u][num]!=-1) return dp[u][num];if(num*p<n-u+1) return -inf;if(num>n-u+1) return -inf;if(num==1){if(n-u+1<=p) return dp[u][num]=a[u];else return -inf;}ll sum=-inf;for(int i=u+1;i<=u+p&&i<=n;i++) sum=max(sum,dfs(i,num-1));if(sum!=-inf) sum+=a[u];return dp[u][num]=sum; } int main() {scanf("%d%d%d",&n,&p,&t);a[0]=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);memset(dp,-1,sizeof(dp));printf("%lld\n",dfs(0,t));return 0; }

根據(jù)記憶化搜索改的非遞歸代碼（動態(tài)規(guī)劃）

#include<bits/stdc++.h> #define ll long long #define inf 1e9 using namespace std;const int maxx=1e3+100; int a[maxx]; ll dp[maxx][maxx]; int n,p,t;int main() {scanf("%d%d%d",&n,&p,&t);a[0]=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);memset(dp,-1,sizeof(dp));for(int i=n;i>=n-p+1&&i>=0;i--) dp[i][1]=a[i];for(int i=n;i>=0;i--){for(int j=2;j<=t;j++){dp[i][j]=-inf;for(int k=i+1;k<=i+p&&k<=n;k++) dp[i][j]=max(dp[i][j],dp[k][j-1]);if(dp[i][j]!=-inf) dp[i][j]+=a[i];}}cout<<dp[0][t]<<endl;return 0; }

ps:如果動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程一開始想不出來的話，我們可以先考慮記憶化搜索的方式，因?yàn)槲腋杏X這種方式是比較好想的，然后根據(jù)記憶化搜索去改寫狀態(tài)轉(zhuǎn)移方程。（自身體會）
努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯]算法提高 第二点五个不高兴的小明（记忆化搜索||动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。