题目描述

塔子哥所在的实验室出了重大科研成果，实验室准备庆祝一下，派塔子哥去买气球装饰场地。

塔子哥走到商店，发现一共有四种颜色的气球：红、黄、蓝、绿。突然他又发现，不同货架上的气球，即使是同种颜色，也会有不同的价格。

思路：动态规划

背包的变种问题。

定义$f[j][t]$表示购买前$j$列的$j$种气球，花费为$t$的方法有多少种。

那么有状态转移方程$f[j][t]=f[j][t]+f[j-1][t-a[i][j]]$，其中，$a[i][j]$为第$i$行第$j$列气球的价格。其意义为：当前$j$列花费为$t$时，枚举当前气球$a[i][j]$，如果购买当前气球，那么会为$f[j][t]$贡献$f[j-1][t-a[i][j]]$（第$j$列买$a[i][j]$花费为$t$，那么第$j-1$列花费为$t-a[i][j]$）。

代码