Stone Game

[3, 4, 5, 6] 每次合并两个石子，所需最少代价。

[3, 9, 6] --> 9

[12, 6] --> 12

[18] --> 18

9 + 12 + 18 = 39

Solution

记忆化搜索的思路，从大到小，先考虑最后的0-n-1合并的总花费

state: dp[i][j]表示把第i到第j个石子合并到一起的最小花费

Function: 预处理sum[i][j]表示i到j所有石子价值和 dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j]) k表示i..j的可分割点

Code

class Solution {
public:
    /**
     * @param A an integer array
     * @return an integer
     */
    int stoneGame(vector<int>& A) {
        // Write your code here
        if(A.size() == 0)
        {
            return 0;
        }

        int n = A.size();

        vector<vector<int>> dp;
        vector<vector<bool>> flag;
        vector<vector<int>> sum;
        for(int i = 0; i<n; i++)
        {
            vector<int> tmp(n, 0);
            vector<bool> tmp2(n, false);
            dp.push_back(tmp);
            flag.push_back(tmp2);

            vector<int> tmp3(n, 0);
            tmp3[i] = A[i];
            sum.push_back(tmp3);
        }

        for(int i = n-1; i >= 0; i--)
        {
            for(int j = i+1; j<n; j++)
            {
                sum[i][j] = sum[i][j-1] + sum[j][j];
            }
        }

        /*
        int ret = memSearch(dp, flag, sum, 0, n-1);
        for(int i = 0; i<dp.size(); i++)
        {
            for(int j = 0; j<dp[i].size(); j++)
            {
                cout<<dp[][]
            }
        }*/

        return memSearch(dp, flag, sum, 0, n-1);
    }

    int memSearch(vector<vector<int>>& dp, vector<vector<bool>>& flag, vector<vector<int>>& sum, int l, int r)
    {
        if(flag[l][r] == true)
        {
            return dp[l][r];
        }

        if(l == r)
        {
            return 0;
        }

        flag[l][r] = true;
        dp[l][r] = numeric_limits<int>::max();

        for(int i = l; i < r; i++)
        {
            dp[l][r] = min(dp[l][r], memSearch(dp, flag, sum, l, i) + memSearch(dp, flag, sum, i+1, r) + sum[l][r]);
        }

        return dp[l][r];
    }
};