前言
對動态規劃最初的認識：是能解決很難的問題，動态規劃是一個很厲害的方法論。
場景
前天做力扣上做一個題目，等級是困難，了解完問題以後，覺得可以使用動态規劃來做，但是自己已經記不清如何使用了。就按照自己能想到的方法開始寫代碼。
題目如下：
你正在安裝一個廣告牌，并希望它高度最大。這塊廣告牌将有兩個鋼制支架，兩邊各一個。每個鋼支架的高度必須相等。
你有一堆可以焊接在一起的鋼筋 rods。舉個例子，如果鋼筋的長度為 1、2 和 3，則可以将它們焊接在一起形成長度為 6 的支架。
傳回廣告牌的最大可能安裝高度。如果沒法安裝廣告牌，請傳回 0。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/tallest-billboard
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
示例 1：
輸入：[1,2,3,6]
輸出：6
解釋：我們有兩個不相交的子集 {1,2,3} 和 {6}，它們具有相同的和 sum = 6。
示例 2：
輸入：[1,2,3,4,5,6]
輸出：10
解釋：我們有兩個不相交的子集 {2,3,5} 和 {4,6}，它們具有相同的和 sum = 10。
示例 3：
輸入：[1,2]
輸出：0
解釋：沒法安裝廣告牌，是以傳回 0。
提示：
0 <= rods.length <= 20
1 <= rods[i] <= 1000
鋼筋的長度總和最多為 5000
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/tallest-billboard
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
我的解體思路是假設每次能用完rods裡的所有鋼筋，那麼rods裡的鋼筋長度加起來需要是偶數total，如果不是偶數，則需要去掉rods裡一根鋼筋再嘗試。如果是偶數，這一堆鋼筋裡能找到一些鋼筋加起來等于total/2，如果不能，再去掉一根鋼筋進行嘗試。
算法采用了遞歸。并通過下面幾種措施減少算的次數：
1、每次算的時候檢查總的高度是否小于已經算出的高度
2、總的高度如果計算過了，就不用再算
3、 尋找total/2的時候，避免重複計算，緩存了計算的值
實作代碼如下：
/**
* @param {number[]} rods
* @return {number}
*/
var tallestBillboard = function(rods) {
const sortrods = rods.sort((a, b) => {
if (a > b) {
return 1
} else if (a === b) {
return 0
} else {
return -1
}
})
let height = 0
const halfMap = {}
// 找到rods裡的數加起來，可以等于half
const findAggregateToHalf = (rods, half) => {
let key = rods.reduce((total, item) => `${total}${item}`)
key += `${half}`
if (halfMap[key] !== undefined) {
return halfMap[key]
}
if (rods.length === 1) {
halfMap[key] = 0
return 0
}
if (rods.length === 2) {
if (rods[0] === half || rods[1] === half) {
halfMap[key] = half
return half
}
return 0
}
for (let i = rods.length - 1; i >= 0; i--) {
if (rods[i] > half) {
halfMap[key] = 0
return 0
}
const newRods = [].concat(rods)
const left = newRods.splice(i, 1)[0]
if (half < left) {
continue
}
if (half === left) {
halfMap[key] = half
return half
}
if (findAggregateToHalf(newRods, half - left)) {
halfMap[key] = half
return half
}
}
halfMap[key] = 0
return 0
}
let max = 0
const getMaxTall = (rods) => {
if (rods.length < 2) {
return 0
}
if (rods.length === 2) {
if (rods[0] === rods[1]) {
return rods[0]
} else {
return 0
}
}
const total = rods.reduce((total, item) => total + item)
if (halfMap[total]) {
return halfMap[total]
}
if (total < (max * 2)) {
return 0
}
if (total % 2 === 0) {
const half = total / 2
if (findAggregateToHalf(rods, half)) {
if (half > max) {
max = half
}
halfMap[total] = half
return half
} else {
// 去掉偶數相等的值，如果有值大于剩下
while(rods[rods.length - 1] > half) {
rods.pop()
}
for (let i = 0; i < rods.length; i++) {
const newrods = [].concat(rods)
newrods.splice(i, 1)
const result = getMaxTall(newrods)
if (result > max) {
max = result
}
}
halfMap[total] = max
return max
}
} else {
for (let i = 0; i < rods.length; i++) {
const newrods = [].concat(rods)
newrods.splice(i, 1)
const result = getMaxTall(newrods)
if (result > max) {
max = result
}
}
halfMap[total] = max
return max
}
}
let data2 = getMaxTall(sortrods)
return data2
};
雖然通過了測試，但是時間和空間消耗都比較悲催
而且代碼可讀性也比較查，應該多個地方含有布丁代碼。而且這個代碼曆時5小時才最終通過了所有測試用例。
第二天
看了官方對題解，第一個方法就是動态規劃，看第一眼很熟悉，但是仔細看，發現沒能看懂官方的方法和狀态轉移方程。
整天都在思考🤔這個解題思路是咋回事，看了其他人的解題思路後，逐漸有了一點了解，于是開始寫自己的版本，官方使用了遞歸來實作，我沒有使用遞歸，而是循環從最小開始往大了找。
大概的是，在 rods裡每增加一根鋼筋，有三種情況，第一種是這個鋼筋用不上，第二種是這跟鋼筋放在左邊的支架，第三種是這個鋼筋放在右邊的支架。那麼增加一根鋼筋後，最大值就在這三種情況裡選了。
這裡有一個細節，就是要記錄每一次放了鋼筋，左邊支架和右邊支架高度還差多少h，已經鋼筋左邊的值。我們使用一個map來記錄，map的key表示h，map[h]表示鋼筋左邊的值。這樣最後的map['0']就是最後的解。
代碼如下：
/**
* @param {number[]} rods
* @return {number}
*/
var tallestBillboard = function(rods) {
const dp = []
let map = {}
for (let i = 0; i < rods.length; i++) {
if (i === 0) {
map['0'] = 0
map[`${-rods[i]}`] = 0
map[`${rods[i]}`] = rods[i]
continue
}
const r = rods[i]
const nMap = {}
for (let key in map) {
nMap[key] = map[key]
}
for (let key in map) {
const value = map[key]
const kn = Number(key)
nMap[`${kn + r}`] = Math.max(value + r, nMap[`${kn + r}`] || 0)
nMap[`${kn - r}`] = Math.max(value, nMap[`${kn - r}`] || 0)
}
map = nMap
}
return map['0'] || 0
};
比第一天的代碼清晰了許多，并且更簡單，當然依然有一些不足的地方。不過時間和空間複雜度得到了比較好的改善。
然後我重新看了一下wiki百科上對動态規劃的描述，總結了兩點：
1、動态規劃用于解決有重疊子問題和最優子結構性質的問題。
2、動态規劃通過把問題分解為子問題，且每個子問題有最優解，通過緩存中間子問題的結果來計算最終的結果，這通常需要推導出狀态轉移方程。
是以下次遇到算法問題，具有重疊子問題和最優子結構問題的時候，就可以考慮使用動态規劃了。
比如下面這個問題：
問題描述
給定一個數字三角形，找到從頂部到底部的最小路徑和。每一步可以移動到下面一行的相鄰數字上。
[2],
[3,4],
[6,5,7],
[4,1,8,3]
從頂到底部的最小路徑和為11 ( 2 + 3 + 5 + 1 = 11)。
輸入：
[[2], [3,4], [6,5,7], [4,1,8,3]]
輸出：
11