Share my both dp and divide conquer solutions

• ``````// dp solution
// dp[i][j] = max(dp[i][j], dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j]; // x from i to j
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.insert(nums.end(), 1);

vector<vector<int> > dp(n+2, vector<int>(n+2, 0));

// k indetify the the body length for dp[i, j]
// travel all the possibility for body length for 1 to n
for (int k = 1; k <= n; k++) {
// [i, j] body length from 1 to n
for (int i = 1; i <= n - k + 1; ++i) {
int j = i + k - 1;
// x between [i, j]
for (int x = i; x <= j; ++x) {
int temp = dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j];
if (temp > dp[i][j]) dp[i][j] = temp;
}
}
}

return dp[1][n];
}

// divide and conquer
int maxCoins1(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.insert(nums.end(), 1);
vector<vector<int> > dp(n+2, vector<int>(n+2, 0));
return DP(1, n, nums, dp);
}

// remember search
int DP(int i, int j, const vector<int> &nums, vector<vector<int>> &dp) {
if (dp[i][j] > 0) return dp[i][j];
for (int x = i; x <= j; ++x) {
int temp = DP(i, x-1, nums, dp) + nums[i-1]*nums[x]*nums[j+1] + DP(x+1, j, nums, dp);
if (temp > dp[i][j]) dp[i][j] = temp;
}
return dp[i][j];
}``````

• Could you tell me ,what is the dp code?

`````` int temp = dp[i][x-1] + nums[i-1]*nums[x]*nums[j+1] + dp[x+1][j];
``````

thx !

• Your divide and conquer is also dynamic programming but top-down instead of bottom-up.

• @clark3 I agree. The divide and conquer shown above is another way of writing bottom-up dp, which is called memoization dp (from top-bottom).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.