这题根 lc 上的不一样,这题给定了糖果数量。因此必定第一步应该就是把 m - 数组长度。 然后剩下的条件你没说全,这 m 个是要全部分完还是允许剩下。这里先假设是全部分完,那么我想到的做法就是回溯,遍历这个数组,在每一个位置上我们都要尝试从放 0 个到放剩下糖果的数量,就等于一个树展开了。 然后全部分完和允许剩下的处理区别就在于遍历到数组最后的时候允不允许再加一罢了。 这题没办法用 DP,因为数组中间的那个量不仅依赖于他自身,还依赖于他后面的量,没有最优子结构。 额。。上面是我的想法,可能有错,可以参考。
点赞 2
牛客网
牛客企业服务