力扣每日一题 卖木头块 线性DP

本文主要是介绍力扣每日一题 卖木头块 线性DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 2312. 卖木头块

思路

👨‍🏫 灵神题解

复杂度

时间复杂度: $O(nm(m+n))$

空间复杂度: $O(nm)$

Code

class Solution {public long sellingWood(int n, int m, int[][] prices) {int[][] pr = new int[n+1][m + 1];for(int[] p : prices)pr[p[0]][p[1]] = p[2];long[][] f = new long[n+1][m+1];for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){f[i][j] = pr[i][j];for(int k = 1; k <= j/2; k++)//垂直切割 f[i][j] = Math.max(f[i][j],f[i][k] + f[i][j-k]);for(int k = 1; k <= i/2; k++)f[i][j] = Math.max(f[i][j],f[k][j] + f[i - k][j]);}return f[n][m];}
}

这篇关于力扣每日一题 卖木头块 线性DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---