题目

burst ballons

2. 算法

* dp

* 递归

3. 代码

* dp

// Non-recursion

class Solution {

public:

    int maxCoins(vector<int>& nums) {

        int n = nums.size();

        nums.insert(nums.begin(), 1);

        nums.push_back(1);

        vector<vector<int> > dp(nums.size(), vector<int>(nums.size() , 0));

        for (int len = 1; len <= n; ++len) {

            for (int left = 1; left <= n - len + 1; ++left) {

                int right = left + len - 1;

                for (int k = left; k <= right; ++k) {

                    dp[left][right] = max(dp[left][right], nums[left - 1] * nums[k] * nums[right + 1] + dp[left][k - 1] + dp[k + 1][right]);

                }

            }

        }

        return dp[1][n];

    }

};

* 递归

// Recursion

class Solution {

public:

    int maxCoins(vector<int>& nums) {

        int n = nums.size();

        nums.insert(nums.begin(), 1);

        nums.push_back(1);

        vector<vector<int> > dp(nums.size(), vector<int>(nums.size() , 0));

        return burst(nums, dp, 1 , n);

    }

    int burst(vector<int> &nums, vector<vector<int> > &dp, int left, int right) {

        if (left > right) return 0;

        if (dp[left][right] > 0) return dp[left][right];

        int res = 0;

        for (int k = left; k <= right; ++k) {

            res = max(res, nums[left - 1] * nums[k] * nums[right + 1] + burst(nums, dp, left, k - 1) + burst(nums, dp, k + 1, right));

        }

        dp[left][right] = res;

        return res;

    }

};