Google 2016 面试题8 吹气球

Google2016面试题，附答案。...

(点击上方关注九章算法，获取最新IT求职干货！)

题目描述

有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。

注释:
(1) 你可以假设nums[-1] = nums[n] = 1
(2) 0 ≤ n ≤ 500, 0 ≤ nums ≤ 100

Example:

给出[3, 1, 5, 8]

返回167

分析解答

如果选择穷举吹气球的顺序，那么需要指数级时间复杂度别的算法才能解决，因此我们要寻求一个更高效的算法。样例中[3,5,8]，因先吹爆分数为3的气球只能得到两个数相乘的分数，先吹爆分数为5的气球反而更优。但是我们可以知道，对于8而言，先吹3再吹5，和先吹5再吹3，都是一样的因为8是最后吹。所以我们，并且如果做过石子合并(http://www.lintcode.com/en/problem/stone-game/)那道题非常相似。因为3和5的问题只在[3,5]区间内，跟区间外面没有关系。因此我们可以用区间dp去解决这个问题。

dp[j]表示吹爆i到j之间的气球所能得到的最大分数。如何转移？那么就穷举先吹爆的气球的编号k，但问题在于，先吹爆气球k会使得k-1号和k+1号气球相邻。那么可以向石子合并那么样反过来。最后吹爆k号气球，这么样我们的dp方程就很好定义了dp[j] = dp[k-1] + score(k) + dp[k+1][j]。先吹区间[i,k]和区间[k+1,j]最后吹k。如果区间[i,k]或者[k+1,j]区间现在还不知道结果怎么办，我们可以用记忆化搜索的方式先去求解。

那么下面我们就总结一下dp的四要素：

Definition:

dp[j]表示吹爆i到j之间的气球所能得到的最大分数

Function:

dp[j] = max(dp[k-1] + score(k) + dp[k+1][j]) 对于所有k属于{i,j}

Intialize:

dp = 0 for each i.

Answer:

dp[1][n]

参考代码

http://www.jiuzhang.com/solutions/bust-ballons/



面试官角度分析

本题中分析的过程很重要，本题是区间DP的好题,首先会考虑暴力的方法，但是时间复杂度特别高。如果面试者做过基础题目Stone Game 并且能够follow up想到这道题区间的性质，发现两题非常类似的话，用n^3的dp算法解决，那么就可以达到hire的程度

相关题目

登陆www.lintcode.com，挑战更多面试真题OJ

http://www.lintcode.com/en/problem/stone-game/

http://www.lintcode.com/en/problem/coins-in-a-line-iii/

Google 2016 面试题 & 解答：点击可阅读

Google 2016 面试题7 | 翻转游戏(Flip Game II)

Google 2016 面试题6 | 数组计数

Google 2016 面试题5 | 岛屿计数2

Google 2016 面试题4 | 矩阵中的最长上升路径

Google 2016 面试题3 | 摆动排序 II

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题1 | 数组补丁

关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等；

简介

九章算法,帮助更多中国人找到好工作!

九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。

目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。

目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。

更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.

    关注 九章算法