小A点菜

题目背景

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

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

题目描述

不过 uim 由于买了一些书，口袋里只剩 元 。

餐馆虽低端，但是菜品种类不少，有 种 ，第 种卖 元 。由于是很低端的餐馆，所以每种菜只有一份。

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4 4
1 1 2 2

样例输出 #1

3

提示

2020.8.29，增添一组 hack 数据 by @yummy

题解

只要理解dp表里装的是方案数，不是剩余钱数或者什么价值，这题就会比较有思路

还有就是输入是没有说只有两行的，要加个有没有输入完的判断

a=[]
# 输入阶段
while len(a)<n_diet:
    a_element=list(map(int,input().split()))
    a=a+a_element

不过我试过了，现在已经修复了，直接这样输入就行，洛谷管理员好快。

a=list(map(int,input().split()))

我也不多说了，直接附上代码吧，如果有看不懂可以私信我洛谷（最好顺便关注我一下）https://www.luogu.com.cn/user/1368189 也可以在评论区评论

# 小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
# https://www.luogu.com.cn/problem/P1164
# 由于小 A 肚子太饿，所以最多只能等待 1 秒  （指的是运行时间限制）

n_diet,m_money=map(int,input().split())
a=[]
# 输入阶段
while len(a)<n_diet:
    a_element=list(map(int,input().split()))
    a=a+a_element

dp=[1]+[0]*(m_money)
for i in range(n_diet):
    diet_cost=a[i]
    for curr_money in range(m_money,0,-1):
        if curr_money >= diet_cost:
            if dp[curr_money-diet_cost] > 0:
                dp[curr_money]+=dp[curr_money-diet_cost]

print(dp[-1])
# AC https://www.luogu.com.cn/record/168499882