dp 问题
参考：leetcode_discuss
c语言代码
int maxCoins(int* nums, int numsSize) {int n = numsSize+2;int *new_nums = (int*)malloc(sizeof(int)*n);new_nums[0] = new_nums[n-1] = 1;for(int i=0;i<numsSize;++i){new_nums[i+1] = nums[i];}int **dp = (int **)malloc(sizeof(int *)*n);for(int i=0;i<n;i++){dp[i] = (int *)malloc(sizeof(int)*n);memset(dp[i],0,sizeof(int)*n);}for(int k=2;k<n;k++){for(int left=0;left<n-k;left++){int right = left+k;for(int i=left+1;i<right;i++){int mid = dp[left][i]+new_nums[left]*new_nums[i]*new_nums[right]+dp[i][right];if(mid>dp[left][right]){dp[left][right] = mid;}}}}return dp[0][n-1];
}
解题记录
