# 3.λ.形而下技术博客

0%

## 题目概述

312原题链接

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

examples:
nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167


## 回顾矩阵链解法

CRLS中在动态规划一章中用了几个例子来详细展示动态规划方法。其中第二个例子就是矩阵链问题————如果有一个 矩阵链A1*A2*A3*A4，其中A1是1x5的矩阵，A2是5x1的矩阵，A3是1x5的矩阵，A4是5x1的矩阵。那么先计算A1*A2A3*A4 则是比较好的，代价较小都是1x5x1=5。而A2*A3则是比较糟糕的，因为A2*A3的计算代价是5x1x5=25