Greedy is wrong and DP is correct
4 min readAug 9, 2020
Leetcode 1547. Minimum Cost to Cut a Stick
Similar to the classical Rod cutting problem
This problem is similar to the rod cutting problem as shown in my post.
1547. Minimum Cost to Cut a Stick
Greedy is wrong
The following greedy algorithm by picking up the cut point which is close to the center is not correct.
typedef pair<int, int> ii;
class Solution {
public:
int minCost(int n, vector<int>& cuts) {
sort(cuts.begin(), cuts.end());
if(cuts.size()<=1)return n;
int ret = 0 ;
priority_queue<ii> pq;
pq.emplace(n, 0);
float best = 0.0;
int bb = 0;
while(!pq.empty())
{
auto [len, begin] = pq.top(); pq.pop();
auto end = begin + len;
if (len==1) continue;
auto it = lower_bound(cuts.begin(), cuts.end(), begin+1);
auto it1 = lower_bound(cuts.begin(), cuts.end(), end-1);
if (it==cuts.end() && it1==cuts.end())continue;
best = begin + len/2.0;
bb = begin + len/2;
auto it3 = lower_bound(cuts.begin(), cuts.end(), bb);
if(it3==cuts.end())
{
bb = cuts.back();
cuts.pop_back();
}
else
{
auto idx = it3 - cuts.begin();
int best_idx = idx;
if(cuts[idx]<end) bb = cuts[idx];
else if (idx==0 || cuts[idx-1]<begin) continue;
else
{
bb = cuts[idx-1];
best_idx = idx - 1;
}
if(idx+1<cuts.size() && cuts[idx+1]<end && cuts[idx+1]>begin)
{
if (abs(cuts[idx] - best) > abs(cuts[idx+1] - best))
{
best_idx = idx+1;
}
}
if(idx-1>=0 && cuts[idx-1]>begin && cuts[idx-1]<end)
{
if (abs(cuts[idx] - best) > abs(cuts[idx-1] - best))
{
best_idx = idx-1;
}
}
bb=cuts[best_idx];
cuts.erase(cuts.begin()+best_idx);
}
ret += len;
pq.emplace(bb-begin, begin);
pq.emplace(end-bb, bb);
}
return ret;
}
};We should use DP instead.
Naive DP get TLE
A naive DP solution gets TLE (45 / 100 test cases passed.)
typedef pair<int, int> ii;
class Solution {
public:
int dp(vector<int>&states, map<vector<int>, int>& memo)
{
if(states.size()==1)
return memo[states] = 0;
if (memo.count(states)) return memo[states];
vector<int> left, right;
int this_ret = states[0]*(states.size());
for(int i=1; i< states.size();++i)
{
left.reserve(i );
left.push_back(states[i]);
for (int k = 1; k < i; ++k)
left.push_back(states[k]);
right.reserve(1 + states.size() -1 - i);
right.push_back(states[0]-states[i]);
for (int k = i+1; k < states.size(); ++k)
right.push_back(states[k]-states[i]);
this_ret = min(this_ret, states[0] + dp(left, memo) + dp(right, memo));
left.clear();right.clear();
}
return memo[states] = this_ret;
}
int minCost(int n, vector<int>& cuts) {
map<vector<int>, int> memo;
vector<int> states;
states.reserve(1+cuts.size());
states.push_back(n);
sort(cuts.begin(), cuts.end());
for (auto x : cuts) states.push_back(x);
return dp(states, memo);
}
};Top-down DP (O(n³))
sort the cuts, we will have cuts0, cuts1 … in sorted order. To make it short, I am using c0 to represent cuts0.
c0_ _ _ _ c1 _ _ _ c2 _ _ _ _ c3 _ _ _c4The above means from left to right, we have 3 positions to cut. We have several cases:
c0_ _ _ _ c1 X(cut here)_ _ _ c2 _ _ _ _ c3 _ _ _c4c0_ _ _ _ c1 _ _ _ c2 X(cut here)_ _ _ _ c3 _ _ _c4c0_ _ _ _ c1 _ _ _ c2 _ _ _ _ c3 X(cut here) _ _c4
Get the minimum res from those 3 cases will get the final results.
For the above case, we will have
res[0][4] = min(res[0][1] + ret[1][4],
res[0][2] + ret[2][4],
res[0][3] + ret[3][4],
)
DP transitions
From the above example, we can find the general transition.
dp[i][j] = min([cuts[j] - cuts[i]+dp[i][k]+dp[k][j] for k in range(i+1, j)])Solution
/**
* time complexity : O(n^3)
* space complexity : O(n^2)
where n is the length of cuts.**/
int memo[110][110];
const int INF = 1e7;
class Solution {
int dp(int i, int j, vector<int>& cuts)
{
if (i >= j) return memo[i][j] = 0;
if (memo[i][j] != -1) return memo[i][j];
if (j - i == 1) return memo[i][j] = 0;
int this_ret = INF;
for (int k = i+1; k < j; ++k)
{
this_ret = min(this_ret, cuts[j] - cuts[i] + dp(i, k, cuts) + dp(k, j, cuts));
}
return memo[i][j] = this_ret ;
}
public:
int minCost(int n, vector<int>& cuts) {
cuts.push_back(0);
cuts.push_back(n);
sort(cuts.begin(), cuts.end());
memset(memo, -1, sizeof memo);
return dp(0, cuts.size()-1, cuts);
}
};
Bottom-up DP
Bottom-up is pretty fast
Runtime: 40 ms, faster than 100.00% of C++ online submissions for Minimum Cost to Cut a Stick.Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Minimum Cost to Cut a Stick.int dp[110][110];
const int INF = 1e7;
class Solution {
public:
int minCost(int n, vector<int>& cuts) {
cuts.push_back(0);
cuts.push_back(n);
sort(cuts.begin(), cuts.end());
const int m = cuts.size();
memset(dp, 0, sizeof dp);
int j;
for (int len = 2; len < m; ++len)
{
for (int i = 0; i < m; ++i)
{
j = i + len;
if (j >= m) continue;
if (len == 2) dp[i][j] = cuts[j] - cuts[i];
else
{
int this_ret = INF;
for (int k = i + 1; k < j; ++k)
{
this_ret = min(this_ret, cuts[j]- cuts[i] + dp[i][k] + dp[k][j]);
}
dp[i][j] = this_ret;
}
}
}
return dp[0][m-1];
}
};
Thanks for reading.
