1 min read
https://practice.geeksforgeeks.org/problems/cutted-segments/0
class Solution {
int dp[10005];
int solve(int x, int a, int b, int c) {
if (dp[x] != -1)
return dp[x];
if (x < min({a, b, c}))
return dp[x] = INT_MIN;
int n1 = (x >= a) ? solve(x - a, a, b, c) + 1 : INT_MIN;
int n2 = (x >= b) ? solve(x - b, a, b, c) + 1 : INT_MIN;
int n3 = (x >= c) ? solve(x - c, a, b, c) + 1 : INT_MIN;
dp[x] = max({n1, n2, n3});
return dp[x];
}
public:
int maximizeTheCuts(int n, int x, int y, int z) {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
solve(n, x, y, z);
return max(0, dp[n]);
}
};