1.312-戳气球

python:

 1 def maxCoins(nums):
 2     """
 3     状态：dp[i][j] 表示戳破[i,j]范围内这些气球所能获得的最大数量的硬币
 4     """
 5     n=len(nums)
 6     nums.insert(0,1)
 7     nums.append(1)
 8     dp=[[0 for i in range(len(nums) )] for j in range(len(nums))]
 9 
10     for span in range(0,n):
11         for i in range(1,n-span+1):
12             j=i+span
13             for k in range(i,j+1):
14                 dp[i][j]=max(dp[i][j],dp[i][k-1]+nums[i-1]*nums[k]*nums[j+1]+dp[k+1][j])
15     print(dp)
16     return dp[1][len(nums)-2]

View Code

思路：

利用动态规划：考虑最后一个被戳破的气球是第k个气球，dp[i][j]表示从第i个气球到第j个气球所能获得的最大收益（包括第j个气球）