5254. 卖木头块 动态规划

5254. 卖木头块

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

• 沿垂直方向按高度 完全 切割木块，或
• 沿水平方向按宽度 完全 切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。

请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。

注意你可以切割木块任意次。

示例 1：

输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。

示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

提示：

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 104
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 10^6
• 所有 (hi, wi) 互不相同 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/selling-pieces-of-wood
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 做题结果

成功，但是周赛时写的太丑了，记忆化搜索，又长又难看，效率还低，所以看群里那么多人说动态规划可以，按动态规划自己写了试了下，快好多，代码又短，觉得自己道行还不够深

 方法1：记忆化搜索

1. 找行列分割点，排序（方便提前跳出）

2. cache 记录是否搜索过，如果搜索过，直接返回

3. 尝试横着切，如果行分割点在当前行数之后，跳过

4. 尝试竖着切，如果列分割点在当前列数之后，跳过

5. 假设刚好这么大，可以不分割，直接用现在的值试试

6. 取横、竖、自己三者最大值返回（此时缓存到cache中）

 class Solution {
        public long sellingWood(int m, int n, int[][] prices) {
            //1.所有的行
            Set<Integer> ls = new HashSet<>();
            Set<Integer> cs = new HashSet<>();

            Map<Integer,Map<Integer,Integer>> mapPrice = new HashMap<>();
            for(int[] price:prices){
                ls.add(price[0]);
                cs.add(price[1]);
                mapPrice.putIfAbsent(price[0],new HashMap<>());
                mapPrice.get(price[0]).put(price[1],price[2]);
            }

            List<Integer> lineList = new ArrayList<>(ls);
            List<Integer> colList = new ArrayList<>(cs);
            Collections.sort(lineList);
            Collections.sort(colList);

            long ans = dfs(lineList,colList,mapPrice,m,n);
            return ans;
        }
        Map<Integer,Long> cache = new HashMap<>();

        private long dfs(List<Integer> lineList,List<Integer> colList, Map<Integer,Map<Integer,Integer>> mapPrice, int m, int n){
            if(cache.containsKey(m*200+n)) return cache.get(m*200+n);
            //按行分割。。。
            long curr = 0L;
            for(int i = 0; i < colList.size()&&colList.get(i)<n; i++){
                long a = dfs(lineList,colList,mapPrice,m,colList.get(i));
                long b = dfs(lineList,colList,mapPrice,m,n-colList.get(i));
                curr = Math.max(curr,a+b);
            }

            for(int i = 0; i < lineList.size()&&lineList.get(i)<m; i++){
                long a = dfs(lineList,colList,mapPrice,lineList.get(i),n);
                long b = dfs(lineList,colList,mapPrice,m-lineList.get(i),n);
                curr = Math.max(curr,a+b);
            }

            //不分
            if(mapPrice.containsKey(m) && mapPrice.get(m).containsKey(n)){
                curr = Math.max(curr,mapPrice.get(m).get(n));
            }
            cache.put(m*200+n,curr);
            return curr;
        }
    }

时间复杂度：O(mn)

空间复杂度：O(mn)

方法2：动态规划

1. 尝试在长度为 i,宽度为 j 的木头上进行切割，如果刚好行列等于当前行列，进行比较赋值

2. 加了当前木头之后，对于原本长宽大于等于它的，都可能获得更优解，每个长宽需要计算按旧方案、按行分割、按列分割三种情形下的更优解

class Solution {
        public long sellingWood(int m, int n, int[][] prices) {
            long[][] dp = new long[m+1][n+1];
            for(int [] price:prices){
                int x = price[0];
                int y = price[1];
                int p = price[2];
                dp[x][y] = Math.max(dp[x][y],p);
                for(int i = x; i <= m; i++){
                    for(int j = y; j <= n; j++){
                        dp[i][j] = Math.max(dp[i][j],Math.max(dp[i-x][j]+dp[x][j],dp[i][j-y]+dp[i][y]));
                    }
                }
            }
            return dp[m][n];
        }
    }

时间复杂度：O(mn)

空间复杂度：O(mn)