https://leetcode.com/problems/selling-pieces-of-wood/
DP，你大爷还是你大爷，重剑无锋，大道至简。
有时候看似很复杂的问题，只要找到DP状态转移方程，也就几行的事情，或许这正是自己要历练的吧。
这道题记下备忘。

个人解答

  1. func sellingWood(m int, n int, prices [][]int) int64 {
  2.     dp := make([][]int64, m + 1) // dp[i][j], 高度为i，宽度为j的板子，可以卖多少钱
  3.     for i := range(dp) {
  4.         dp[i] = make([]int64, n + 1)
  5.     }
  7.     for _, p := range(prices) {
  8.         dp[p[0]][p[1]] = int64(p[2])
  9.     }
  11.     for i := 1; i <= m; i++ {
  12.         for j := 1; j <= n; j++ {
  13.             for cutH := 1; cutH < i; cutH++ {
  14.                 if dp[i][j] < dp[cutH][j] + dp[i - cutH][j] {
  15.                     dp[i][j] = dp[cutH][j] + dp[i - cutH][j]
  16.                 }
  17.             }
  18.             for cutV := 1; cutV < j; cutV++ {
  19.                 if dp[i][j] < dp[i][cutV] + dp[i][j - cutV] {
  20.                     dp[i][j] = dp[i][cutV] + dp[i][j - cutV]
  21.                 }
  22.             }
  23.         }
  24.     }
  26.     return dp[m][n]
  27. }

题目分析

这道题目有个关键的一点：

To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces.

必须全部切开，因此可以就横着的和竖着的分开处理，两个合起来就是最终的结果。
因此DP状态转移就比较容易想到了：

  1. # 横着切一刀，两个卖的钱加起来
  2. dp[i][j] = max(dp[i][j], dp[cutH][j] + dp[i - cutH][j])
  3. # 竖着切一刀，两个卖的钱加起来
  4. dp[i][j] = max(dp[i][j], dp[i][cutV] + dp[i][j - cutV])

大道至简，就这样，就解决了问题。
初始条件的话，不就是给的那些板子么，如此优雅。