这是一道很水的dp题,但作为第一天学动态规划的蒟蒻还是提交了两遍/捂脸/

看到前面dalao全部用文字叙述,今天我想介绍一种推状态转移方程的方法————

表格法

直观的表格
本人直接用的样例,方便对照

通过表格可以直观看出方程 自认为小学找规律难度

具体数据表示啥我就不详细介绍了,应该都懂
还是上一下代码吧:

#include<cstdio>
using namespace std;
const int maxm = 10005, maxn = 105;  //数据范围
int cell[maxn][maxm], p[maxn];
int main()
{
	int m, n;
	scanf("%d%d", &n, &m);  //看清输入顺序,我第一次就是把顺序搞反了
	for(int i=1; i<=n; ++i)
		scanf("%d", &p[i]);  //输入价格
	for(int i=1; i<=n; ++i)    //从第一道菜开始(表格第一列)
		for(int j=1; j<=m; ++j)   //从只剩一元钱开始直到符合输入的钱数(表格第一行)
		{
			if(j < p[i])   //三个方程依次判断
				cell[i][j] = cell[i-1][j];
			if(j == p[i]) 
				cell[i][j] = cell[i-1][j]+1;
			if(j > p[i]) 
				cell[i][j] = cell[i-1][j]+cell[i-1][j-p[i]];
		}
	printf("%d", cell[n][m]);  //由上表可得:右下角的数即为正解
	return 0;  //愉快的结束
}