- All problems,
- Palindrome problems are a subset of Longest Common Subsequence problems.
- substring vs subsequence: substring is continuous and subsequence can be discontinuous.
- To start with recursive solution, we needbase_casechoice_diagram and decreasing input.
- To find thebase_case don’t create the whole recursion tree like this, it will confuse you, consider the smallest possible input
- As per above smallest possible input here can be 0, if the two strings among whom the longest common subsequence has to be found are empty "" then the output is going to be "". sobase_case is if (n 0 || m 0) return 0
- if the last character of both strings is equal then reduce their length by 1 and add the matching string to result set.
- choice_diagram
- if both the string char match then add 1 since it is a match and we have to return the longest matching string and call lcs with original strings and the lengths subtracted by 1.
- else reduce count by 1 of one of the strings, call LCS() with reducing 1 from n or m and taking max from either of these two.
- Smaller input in every recursive version.
- Now the same things as in Knapsack problem, create a matrix, initialise with minimal values and then assign the values calculated by recursion, basically just put the assignment before the return statement.
- overlapping_subproblems
- m and n are changing, size of grid is going to be m + 1 and n + 1, why +1? Because we are also calculating for 0,
- Because of the difference in length and index. If we would have created m x n table then space to store would have been (m - 1) x (n - 1)
- Depending on constraint, initialise the matrix,
- Recursion memoization is alwaysTop_Down (and not bottom up), as we take a bigger problem and recursively solve for the smaller subproblems. Whereas in tabular DP where we start filling the table from top left to bottom right is actuallyBottom_Up because we compute dp values of smaller subproblems first and then using these values compute dp value of bigger problems
- 2^n → n x n
- tabulation isBottom_Up
- Breaking intooverlapping_subproblems
- This is the equation to fill a block, to fill the whole array put a loop on it,
- Start loop from 1 since we had already fill the 0th row and column with 0 initial values.
