为了提高智商ZJY开始学习组合数学.某一天她解决了这样一个问题:给一个网格图其中某些格子有财宝.每次从左上角出发只能往右或下走.问至少要走几次才可能把财宝全捡完.
但是她还不知足想到了这个问题的一个变形:假设每个格子中有好多块财宝而每一次经过一个格子至多只能捡走一块财宝其他条件不变至少要走几次才可能把财宝全捡完?
这次她不会做了你能帮帮她吗?
每组数据的第一行是两个正整数n和m表示这个网格图有n行m列.
接下来n行每行m个非负整数表示这个格子中的财宝数量(0表示没有财宝).
输出格式:
对于每组数据输出一个整数表示至少走的次数.
对于30%的数据n≤5.m≤5每个格子中的财宝数不超过5块.
要算至少取几次能取完,
我们考虑有哪一些财宝是不能同一次取的.
由于原题要求是从左上到右下的,我们就从右上到坐下走,寻找一次性不能取的.
这种类型题,我们考虑dp.
我们知道(ij)和右上(i-1j)是不能同时取的,
最终dp转移是这样的;