# 这个前端竟然用动态规划写瀑布流布局？给我打死他！

## 准备工作

``````let SISTERS = [
'https://pic3.zhimg.com/v2-89735fee10045d51693f1f74369aaa46_r.jpg',
'https://pic1.zhimg.com/v2-ca51a8ce18f507b2502c4d495a217fa0_r.jpg',
'https://pic1.zhimg.com/v2-c90799771ed8469608f326698113e34c_r.jpg',
'https://pic1.zhimg.com/v2-8d3dd83f3a419964687a028de653f8d8_r.jpg',
... more 50 items
]``````

``````let loadImgHeights = (imgs) => {
return new Promise((resolve, reject) => {
const length = imgs.length
const heights = []
let count = 0
const load = (index) => {
let img = new Image()
const checkIfFinished = () => {
count++
if (count === length) {
resolve(heights)
}
}
img.onload = () => {
const ratio = img.height / img.width
const halfHeight = ratio * halfInnerWidth
// 高度按屏幕一半的比例来计算
heights[index] = halfHeight
checkIfFinished()
}
img.onerror = () => {
heights[index] = 0
checkIfFinished()
}
img.src = imgs[index]
}
imgs.forEach((img, index) => load(index))
})
}``````

## 贪心算法

``````let greedy = (heights) => {
let leftHeight = 0
let rightHeight = 0
let left = []
let right = []
heights.forEach((height, index) => {
if (leftHeight >= rightHeight) {
right.push(index)
rightHeight += height
} else {
left.push(index)
leftHeight += height
}
})
return { left, right }
}``````

``````<div class="wrap" v-if="imgsLoaded">
<div class="half">
<img
class="img"
v-for="leftIndex in leftImgIndexes"
:src="https://segmentfault.com/a/1190000022913091/imgs[leftIndex]"
:style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }"
/>
</div>
<div class="half">
<img
class="img"
v-for="rightIndex in rightImgIndexes"
:src="https://segmentfault.com/a/1190000022913091/imgs[rightIndex]"
:style="{ width: '100%', height: imgHeights[rightIndex] + 'px' }"
/>
</div>
</div>``````

https://sl1673495.github.io/d…

## 动态规划

``````dp[heights][height] = max(
// 选择当前图片放入列中
currentHeight + dp[heights - 1][height - currnetHeight],
// 不选择当前图片
dp[heights - 1][height]
)``````

### 小问题拆解

1. 首先去尝试凑高度 `1`：我们知道图片 1 的高度正好是 1，所以此时`dp[0][0]`所填写的值是 `{ max: 1, indexes: [0] }`，也就代表用总高度还剩 1，并且只考虑图片 1 的情况下，我们的最优解是选用第一张图片。
2. 凑高度`2 ~ 7`：由于当前只有 1 可以选择，所以最优解只能是选择第一张图片，它们都是 `{ max: 1, indexes: [0] }`
``````高度       1  2  3  4  5  6  7

``````let mid = Math.round(sum(heights) / 2)
let dp = []
// 基础状态 只考虑第一个图片的情况
dp[0] = []
for (let cap = 0; cap <= mid; cap++) {
dp[0][cap] =
heights[0] > cap
? { max: 0, indexes: [] }
: { max: heights[0], indexes: [0] }
}``````

``````高度       1  2  3  4  5  6  7

1. 选择当前图片，那么假设当前要凑的总高度为 3，当前图片的高度为 2，剩余的高度就为 1，此时我们可以用剩余的高度去「上一个纵坐标」里寻找「只考虑前面几种图片」的情况下，高度为 1 时的最优解。并且记录 `当前图片的高度 + 前几种图片凑剩余高度的最优解``max1`
2. 不选择当前图片，那么就直接去「只考虑前面几种图片」的上一个纵坐标里，找到当前高度下的最优解即可，记为 `max2`
3. 比较 `max1``max2`，找出更大的那个值，记录为当前状态下的最优解。

1. 凑高度 1：由于图片 2 的高度为 2，相当于是容量超了，所以这种情况下不选择图片 2，而是直接选择图片 1，所以 `dp[1][0]` 可以直接沿用 `dp[0][0]`的最优解，也就是 `{ max: 1, indexes: [0] }`
2. 凑高度 2：

1. 选择图片 2，图片 2 的高度为 4，能够凑成的高度为 4，已经超出了当前要凑的高度 2，所以不能选则图片 2。
2. 不选择图片 2，在只考虑图片 1 时的最优解数组 `dp[0]` 中找到高度为 2 时的最优解： `dp[0][2]`，直接沿用下来，也就是 `{ max: 1, indexes: [0] }`
3. 这种情况下只能不选择图片 2，而沿用只选择图片 1 时的解， `{ max: 1, indexes: [0] }`
3. 省略凑高度 `3 ~ 4` 的情况，因为得出的结果和凑高度 2 是一样的。
4. 凑高度 5：高度为 5 的情况下就比较有意思了：

1. 选择图片 2，图片 2 的高度为 4，能够凑成的高度为 4，此时剩余高度是 1，再去只考虑图片 1 的最优解数组 `dp[0]`中找高度为 1 时的最优解`dp[0][1]`，发现结果是 `{ max: 1, indexes: [0] }`，这两个高度值 4 和 1 相加后没有超出高度的限制，所以得出最优解：`{ max: 5, indexes: [0, 1] }`
2. 不选择图片 2，在图片 1 的最优解数组中找到高度为 5 时的最优解： `dp[0][5]`，直接沿用下来，也就是 `{ max: 1, indexes: [0] }`
3. 很明显选择图片 2 的情况下，能凑成的高度更大，所以 `dp[1][2]` 的最优解选择 `{ max: 5, indexes: [0, 1] }`

`dp[3][7]` 的推理过程是这样的：

1. 用最后一张高度为 4 的图片，加上前三张图片在高度为 7 – 4 = 3 时的最优解也就是 `dp[2][3]`，得到结果 4 + 1 = 5。
2. 不用最后一张图片，直接取前三张图片在高度为 7 时的最优解，也就是 `dp[2][7]`，得到结果 6。
3. 对比这两者的值，得到最优解 6。

``````// 尽可能选出图片中高度最接近图片总高度一半的元素
let dpHalf = (heights) => {
let mid = Math.round(sum(heights) / 2)
let dp = []
// 基础状态 只考虑第一个图片的情况
dp[0] = []
for (let cap = 0; cap <= mid; cap++) {
dp[0][cap] =
heights[0] > cap
? { max: 0, indexes: [] }
: { max: heights[0], indexes: [0] }
}
for (
let useHeightIndex = 1;
useHeightIndex < heights.length;
useHeightIndex++
) {
if (!dp[useHeightIndex]) {
dp[useHeightIndex] = []
}
for (let cap = 0; cap <= mid; cap++) {
let usePrevHeightDp = dp[useHeightIndex - 1][cap]
let usePrevHeightMax = usePrevHeightDp.max
let currentHeight = heights[useHeightIndex]
// 这里有个小坑 剩余高度一定要转化为整数 否则去dp数组里取到的就是undefined了
let useThisHeightRestCap = Math.round(cap - heights[useHeightIndex])
let useThisHeightPrevDp = dp[useHeightIndex - 1][useThisHeightRestCap]
let useThisHeightMax = useThisHeightPrevDp
? currentHeight + useThisHeightPrevDp.max
: 0
// 是否把当前图片纳入选择 如果取当前的图片大于不取当前图片的高度
if (useThisHeightMax > usePrevHeightMax) {
dp[useHeightIndex][cap] = {
max: useThisHeightMax,
indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex),
}
} else {
dp[useHeightIndex][cap] = {
max: usePrevHeightMax,
indexes: usePrevHeightDp.indexes,
}
}
}
}
return dp[heights.length - 1][mid]
}``````

``````this.leftImgIndexes = dpHalf(imgHeights).indexes
this.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes)``````

## ❤️ 感谢大家

1.如果本文对你有帮助，就点个赞支持下吧，你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友，我拉你进「前端进阶交流群」，大家一起共同交流和进步。