leetcode312 戳气球
这一题可以用动态规划来解决,但是dp含义的设置和状态转移方程的设计很有意思。
首先,一维dp难以实现的,应该考虑二维dp,尤其在一个数组中,要考虑到双指针移动来解决复杂问题。
如果将dp[i][j]
的含义设置为戳爆下标[i,j]
之间所有的气球能获得的最大钱币,会发现由于涉及到与i左边和j右边数字相乘,难以书写状态转移方程。
将dp[i][j]
的含义设置为:戳爆下标i和j之间(开区间)的所有气球能获得的最大钱币。此时,如果将状态转移方程写为
d
p
[
i
]
[
j
]
=
m
a
x
(
先
戳
气
球
k
,
再
戳
剩
下
所
有
气
球
,
获
得
的
最
大
钱
币
)
i
<
k
<
j
dp[i][j]=max(先戳气球k,再戳剩下所有气球,获得的最大钱币) i<k<j
dp[i][j]=max(先戳气球k,再戳剩下所有气球,获得的最大钱币)i<k<j,会造成子问题之间相互牵连,不具有独立性,也就无法完成动态规划的设计。
因此将状态转移方程方程写成dp[i][j]=max(先戳剩下所有气球,再戳气球k,获得的最大钱币) i<k<j
,这样每次左右两边的计算互不干扰,即可完成动态规划的设计。
(本质是由于,如果先戳爆气球k,则气球k-1右侧的气球改变,气球k+1左侧的气球也改变,造成钱币获取公式的改变,而最后戳爆气球k,则不会出现这个问题,即固定了dp[i][j]中i和j这两个气球)
class Solution {
public:
vector<int>nums;
int stab(int t){
if(t==0 || t==nums.size()+1)
return 1;
return nums[t-1];
}
int maxCoins(vector<int>& nums) {
this->nums=nums;
int n=nums.size();
vector<vector<int>>dp(n+2,vector<int>(n+2,-1));
for(int i=0;i<=n+1;i++)
for(int j=i;j>=0;j--){
if(i==j || i==j+1){
dp[j][i]=0;
}
else{
int m=0;
for(int k=j+1;k<i;k++){
m=max(m,dp[j][k]+dp[k][i]+stab(i)*stab(k)*stab(j));
}
dp[j][i]=m;
}
}
return dp[0][n+1];
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)