Readme

2312.Selling-Pieces-of-Wood

令dp[i][j]表示高度为i、宽度为j的矩形所能得到的最大收益。因为任何一刀必须贯穿整块木板，并且两块木板可以继续各自独立地做进一步操作。显然这就是状态的转移。

假设这一刀是竖切，那么假设左半部分的宽度是k，那么就分成了大小为[i,k]和[i,j-k]的两部分。类似的，如果这一刀是横切，假设上半部分的高度是k，那么就分成了大小为[k,j]和[i-k,j]的两部分。所以我们只要从小到大遍历高和宽，就可以求出所有的dp[i][j].

边界条件是某些特定的高和宽恰好对应了prices里面的形状，那么他们的dp值除了可以通过上述分割的转移方程进行推导，也可以从prices里面得到。两者取大即可。