PROBLEM LINK:
Author: Satyam Gupta
Editorialist: Satyam Gupta
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, Strings
PROBLEM:
Given a string denoting candies in a line, output the minimum number of turns to put all candies in a basket, such that only consecutive substring that makes a palindrome can be lifted up in a single turn.
EXPLANATION:
char input_str[510];
int dp[510][510];
//1. dp_solve(left, right) gives minimum moves for range left to right
int dp_solve(int left, int right) {
//2. terminating condition, why this gives correct result when it returns 1? We’ll understand later in comment 5
if (left >= right)
return 1;
//3. If solution for range [left,right] is already calcuated/memoized, then return it
if (dp[right])
return dp[right];
//4. Worst case is removing every character, one by one
int ans = right - left + 1;
//5. If we know the solution for range in between left and right excluding ends, then in that solution, the last move removed the last palindrome, that means if str==str[right], then these both characters can be included in the last move that was used in solution for str[left+1 to right-1]
if (input_str == input_str[right])
ans = min(ans, dp_solve(left + 1, right - 1));
//6. Solve for all possible 2 partitions, which will further divide in every possible segment as it goes down the recursion, and return the min.
for (int i = left; i < right; i++)
ans = min(ans, dp_solve(left, i) + dp_solve(i + 1, right));
dp[right] = ans;
return ans;
}
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.