golang刷leetcode: 賣(mài)木頭塊

給你兩個(gè)整數(shù) m 和 n ，分別表示一塊矩形木塊的高和寬。同時(shí)給你一個(gè)二維整數(shù)數(shù)組 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的價(jià)格賣(mài)一塊高為 hi 寬為 wi 的矩形木塊。

每一次操作中，你必須按下述方式之一執(zhí)行切割操作，以得到兩塊更小的矩形木塊：

沿垂直方向按高度 完全 切割木塊，或

沿水平方向按寬度 完全 切割木塊

在將一塊木塊切成若干小木塊后，你可以根據(jù) prices 賣(mài)木塊。你可以賣(mài)多塊同樣尺寸的木塊。你不需要將所有小木塊都賣(mài)出去。你 不能 旋轉(zhuǎn)切好后木塊的高和寬。

請(qǐng)你返回切割一塊大小為 m x n 的木塊后，能得到的 最多 錢(qián)數(shù)。

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

示例 1：

輸入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]

輸出：19

解釋：上圖展示了一個(gè)可行的方案。包括：

- 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 元是最多能得到的錢(qián)數(shù)。

示例 2：

輸入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]

輸出：32

解釋：上圖展示了一個(gè)可行的方案。包括：

- 3 塊 3 x 2 的小木塊，售出 3 * 10 = 30 元。

- 1 塊 1 x 4 的小木塊，售出 1 * 2 = 2 元。

總共售出 30 + 2 = 32 元。

32 元是最多能得到的錢(qián)數(shù)。

注意我們不能旋轉(zhuǎn) 1 x 4 的木塊來(lái)得到 4 x 1 的木塊。

提示：

1 <= m, n <= 200

1 <= prices.length <= 2 * 104

prices[i].length == 3

1 <= hi <= m

1 <= wi <= n

1 <= pricei <= 106

所有 (hi, wi) 互不相同 。

解題思路：

1，dp[i][j]表示寬為j高為i的最大價(jià)值，我們可以用prices初始化我們分切出每一個(gè)矩形的價(jià)值

2，對(duì)于每一個(gè)位置高度i，我們可以從k的位置切開(kāi)（0<k<i）,最大價(jià)值就是max( dp[i][j], dp[k][j]+ dp[i-k][j])

3，對(duì)于每一個(gè)位置高度j，我們可以從k的位置切開(kāi)（0<k<j）,最大價(jià)值就是

max(dp[i][j], dp[i][k]+dp[i][j-k])

4，由于每個(gè)位置都依賴比它低的位置，因此遞增

代碼實(shí)現(xiàn)：

func sellingWood(m int, n int, prices [][]int) int64 {  dp:=make([][]int64,m+1)  for i:=1;i<=m;i++{      dp[i]=make([]int64,n+1)  }  for _,price:=range prices{      dp[price[0]][price[1]]=int64(price[2])  }
  for i:=1;i<=m;i++{      for j:=1;j<=n;j++{          for k:=1;k<i;k++{            dp[i][j]=max( dp[i][j], dp[k][j]+ dp[i-k][j])          }          for k:=1;k<j;k++{             dp[i][j]=max(dp[i][j], dp[i][k]+dp[i][j-k])          }      }  }  return dp[m][n]}
func max(a,b int64)int64{    if a>b{        return a    }    return b}

推薦閱讀

• golang刷leetcode: 小于等于 K 的最長(zhǎng)二進(jìn)制子序列