例1:

有6个关卡, 2个通道, 每次可以跳3关或者跳3关. 那么第i关的积分来自于i-2和i-3关卡之间取最大值.

动态规划解题思路五步:

第一步、讲问题可视化, 画出图示:

第二步、找到合适的子问题： 第i步做多能获得多少分？

第三步、找子问题之间的关系： 第i步的最大分值等于a [i-j] (1<=j<=M)的最大值加上a[i]的值。

第四步：按顺序解决子问题：

for(int i=1;i<=n;i++){
  for(int j=1;j<=m;j++){
    b[i]=a[i-j]+a[i]; 
  }
}

最终满分代码：

#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
int n;//n个关卡 
int m; //每关m个通道 
int a[101]; //可以跳a[i]关 
int b[20001]; //关卡分值 
int c[20001]; //累计最大分值 
int main() {
	
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		cin >> b[i];
	for (int i = 1; i <= n * 2; i++)
		c[i] = -1000000000;
	for (int i = 0; i <= n * 2; i++) { //最大值可能出现在跳关情况 
		int mx = 0 - pow(2, 32);
		//cout << "\n mx=" << mx << endl;
		for (int j = 0; j < m; j++) {
			if (i - a[j] >= 0) {
				mx = max(mx, c[i - a[j]] + b[i-a[j]]);
			}
		}
		c[i] = max(c[i], mx);
	}
	//调试代码 
	/*for (int i = 0; i <= 2 * n; i++)
		cout << b[i] << " ";
	cout << endl;
	for (int i = 0; i <= 2 * n; i++)
		cout << c[i] << " ";*/
	//cout << endl;

	int ans = -1000000000;
	for (int i = n; i <= 2 * n; i++)
		ans = max(ans, c[i]);
	cout << ans;
	return 0;
}

【P10108 [GESP202312 六级] 闯关游戏】 https://www.bilibili.com/video/BV18WdbYLE8B/?share_source=copy_web&vd_source=63c3ee2abc19603a42b50d5996e3febc