牛客对应题目链接：取金币_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
- 区间 dp：为了方便能处理边界情况，将原数组前后添加⼀个 1，并不影响最后相乘的结果。
- 状态表示：dp[i][j] 表示：[i, j] 区间⼀共能获得多少金币。
- 填表顺序：从下往上，从左往右。
二、代码
//值得学习的代码
class Solution
{int arr[110] = { 0 };int dp[110][110] = { 0 };public:int getCoins(vector<int>& coins) {int n = coins.size();arr[0] = arr[n + 1] = 1;for(int i = 1; i <= n; i++) arr[i] = coins[i - 1];for(int i = n; i >= 1; i--){for(int j = i; j <= n; j++){for(int k = i; k <= j; k++){dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);}}}return dp[1][n];}
};//牛客
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param coins int整型vector * @return int整型*/int getCoins(vector<int>& coins) {int n=coins.size();vector<vector<int>> dp(n+2, vector<int>(n+2, 0));vector<int> a(n+2, 0);for(int i = 1; i <= n; i++)a[i]=coins[i-1];a[0]=a[n+1]=1;for(int i=n; i>=1; i--){for(int j=i; j<=n; j++){for(int k=i; k<=j; k++){dp[i][j]=max(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[i-1]*a[k]*a[j+1]);}}}return dp[1][n];}
};三、反思与改进
找到子问题，就可以知道这道题目考察的是区间 dp。