LEVIOSA - Editorial

PROBLEM LINK:

Practice
Contest

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.