Leetcode 1547. Minimum Cost to Cut a Stick

 https://leetcode.com/problems/minimum-cost-to-cut-a-stick/description/

Notes:

One way to think about this question is to down-size the question: for example, if we cut the wood [0, m] at position i, then it becomes two parts: the first part is [0, i], and the second part is [i, m], then we need to do the same thing to the first and second parts until it cannot be cut any more.

If we define dp[0][m] is the minimum cost to cut the wood from 0 to m, and there are several choices, then 

dp[0][m] = min(dp[0][m], dp[0][i] + dp[i][m])    where i>0 and i<m

dp[0][i] means the minimu cost to cut the wood from 0 to i with the same rule.

dp[i][m] means the minimu cost to cut the wood from i to m with the same rule.

The general formula becomes: 

dp[a][b] = min(dp[a][b], dp[a][i] + dp[i][b]), where i > a && i < b

See the code below:

class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        // dp[0][n-1] = min(dp[0][i] + dp[i][n-1]) + cuts[n-1] - cuts[0] + 1;
        sort(cuts.begin(), cuts.end());
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);
        int m = cuts.size();
        vector<vector<int>> dp(m, vector<int>(m, 0));
        for(int i=2; i<m; ++i) {
            for(int j=i-2; j>=0; --j) {
                dp[j][i] = INT_MAX;
                for(int k=j+1; k<i; ++k) {
                    dp[j][i] = min(dp[j][i], dp[j][k] + dp[k][i]);
                }
                dp[j][i] += cuts[i] - cuts[j];
            }
        }
        return dp[0][m-1];
    }
};