动态规划
薯券使用问题
http://www.nowcoder.com/questionTerminal/61d87f7f514a4687859a837578ef3aca
动态规划：
f(i,j)表示选择前i种商品构成消费券价值为j的方案数量，price_i表示第i种商品的价格。
状态转移：
f(i,j) = f(i-1,j)+ f(i-1,j-1price_i)...+f(i-1,j-kprice_i), k=(j/price_i)
因为
f(i,j-price_i) = f(i-1,j-price_i)+.....+f(i-1,j-k*price_i)
故状态转移方程：
f(i,j) = f(i-1,j)+f(i,j-price_i)
str1 = input() arr = str1.split() # 购物券的价格 money = int(arr[0]) # 获取商品的价格列表 price = [int(i) for i in arr[1] if i.isdigit()] # 商品列表长度 n = len(price) # 记录状态值 dp = [[0 for i in range(money+1)]for j in range(n+1)] for i in range(1,n+1): dp[i][0] = 1 # 给定初始值 for i in range(1,n+1): for j in range(1,money+1): dp[i][j] = dp[i-1][j] if j>=price[i-1]: dp[i][j]+=dp[i][j-price[i-1]] print(dp[-1][-1])
但是只能通过90%的案例，最后一个结果案例的结果比较大，应该要对其取相应的余数，但是题目没有告诉。
查看10道真题和解析
