吉林大学学风建设专题网站,wordpress 锚文点,望野翻译,辽宁招投标工程信息网Problem P27. [算法课动态规划] 戳气球 有 n 个气球#xff0c;编号为0 到 n - 1#xff0c;每个气球上都标有一个数字#xff0c;这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球#xff0c;你可以获得 nums[i−1]nums[i]nums[i1] 枚硬币。 这里的…Problem P27. [算法课动态规划] 戳气球 有 n 个气球编号为0 到 n - 1每个气球上都标有一个数字这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球你可以获得 nums[i−1]×nums[i]×nums[i1] 枚硬币。 这里的 i - 1 和 i 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i 1 超出了数组的边界那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量
提示
n nums.length 1 n 300 0 nums[i] 100 题目数据保证运算过程不超过 int 所能表示的范围 输入
输入一行数组num
输出
输出所能获得硬币的最大数量
样例
标准输入 3 1 5 8 标准输出 167 标准输入 1 5 标准输出 10
参考视频这个视频讲的非常好再配上我的注释就很容易看懂了搞了一个晚上终于搞懂了琢磨了好久网上好多资料都看不懂我太菜了呜呜呜
#include iostream
#include bits/stdc.husing namespace std;
int dp[310][310];int main()
{int d;vectorint nums;while(cin d){nums.push_back(d);}int n nums.size();//头尾记上不能戳爆的气球为1nums.insert(nums.begin(), 1);nums.push_back(1);memset(dp, 0, sizeof dp);//从长度为1的区间开始推导到长度为n计算区间内获得的最大金币//所有的小段所有的开始位置有了小段的长度同时就可以指导截止位置了都进行求max/*举例n10取长度为1即len1则可以取十组分别是1-10开始位置也是从1-10即第二层循环leftn-len1即left10-1110进行10次len2取12,23,34....910第二层循环截止位置left10-219;len3取123,234...8910第二层循环截止位置left10-318rightleftlen-1比如234-》right23-14依次递推...接着从取到的每一小段当中逐个寻找合适的k取max注意是nums[left-1]*nums[k]*nums[right1]取边left和right外的*/for(int len1; lenn; len){for(int left1; leftn-len1; left){int right leftlen-1;for(int kleft; kright; k){dp[left][right] max(dp[left][right], dp[left][k-1]dp[k1][right]nums[left-1]*nums[k]*nums[right1]);}}}cout dp[1][n];
// cout Hello world! endl;return 0;
}
