dp。P1164 小A点菜 ，洛谷

题目背景

uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。

uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过 uim 由于买了一些书，口袋里只剩 �M 元 (�≤10000)(M≤10000)。

餐馆虽低端，但是菜品种类不少，有 �N 种 (�≤100)(N≤100)，第 �i 种卖 ��ai​ 元 (��≤1000)(ai​≤1000)。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 11 秒。

输入格式

第一行是两个数字，表示 �N 和 �M。

第二行起 �N 个正数 ��ai​（可以有相同的数字，每个数字均在 10001000 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

输入输出样例

输入 #1复制

4 4
1 1 2 2

输出 #1复制

3

定义一个二维数组f[n][m]

f[i][j]表示前i个菜花掉j元的方案数

则各种情况的判断如下：

        if (j == arr[i])
                f[i][j] = f[i - 1][j] + 1;
         else if (j > arr[i])
                f[i][j] = f[i - 1][j] + f[i - 1][j - arr[i]];
        else

                f[i][j] = f[i - 1][j];

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<map>


using namespace std;
typedef long long LL;

const int MAXN = 3e4 + 5;
int f[102][10002];
int arr[1005];


int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j == arr[i])
				f[i][j] = f[i - 1][j] + 1;
			else if (j > arr[i])
				f[i][j] = f[i - 1][j] + f[i - 1][j - arr[i]];
			else
				f[i][j] = f[i - 1][j];
		}
	}

	


	printf("%d\n", f[n][m]);
	return 0;
}

dp很烧脑！！！QAQ