题目
分析
看到这个问题的第一反应可能会有以下想法:只要每一步,都加最小值,就能得到最优解。
上述思路即贪心算法的核心思路:局部最优。
对于示例来说看起来是正确的,然而如果三角形长这样呢?
此时再用贪心算法的思路得到的解就不再是全局最优解了,这也证明了一点:每一次的局部最优走到最后并不一定是全局最优。
对于这种寻找全局最优解的思路通常是动态规划(DP),而这种思路的特点是自下而上,以示例中的三角形为例(这里将三角形倒过来,方便说明):
这里我们可以先计算出前两行的最优解:
6 + min(4, 1) = 7
5 + min(1, 8) = 6
7 + min(8, 3) = 10
此后可以得到下一步的结果:
依次类推,可以得到最后的结果是 11。
那么按照上述思路就能得到最终结果了:
const minimumTotal = (triangle) =>
triangle.reduceRight((pre, cur) =>
cur.map((n, i) => n + Math.min(pre[i], pre[i + 1]))
)[0];
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!