LeetCode 312 题目解答:题目的意思其实就是通过设定踩爆的气球的顺序来获得最多的硬币数。由于这个题目的分组是在分治算法上,所以这个题肯定是要用分治算法的。
但后来发现这道题需要采用动态规划的思想。通过设立一个二维数组 result[i][j] 来表示踩爆两个气球之间的可以获得的最大硬币数。最后返回 result[0][n-1] 来表示结果。注意一个点是可以利用最后一个被踩爆的气球来将问题分为两个独立的子问题来计算。
Code
- class Solution {
- public: int maxCoins(vector & nums) {
- int n = nums.size() + 2;
- int result[n][n];
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/03-03/17999235.html