Here is the comparison of using memoization and tabulation for the various problems:
| Problem | Memoization | Tabulation | Preferred | Explanation |
|---|---|---|---|---|
| Egg dropping problem | O(nk^2) | O(nk) | Tabulation | Memoization has higher time complexity than tabulation due to the recursive nature of the problem. The space complexity of memoization is higher than tabulation as it uses recursion stack. |
| Binomial Coefficient | O(nk) | O(nk) | Either | Both memoization and tabulation have the same time and space complexity. Memoization can be preferred for small values of n and k. Tabulation can be preferred for larger values of n and k as it is an iterative approach. |
| Rod cutting problem | O(n^2) | O(n^2) | Either | Both memoization and tabulation have the same time and space complexity. Either approach can be preferred as per the preference of the programmer. |
| Subset Sum | O(nW) | O(nW) | Either | Both memoization and tabulation have the same time and space complexity. Either approach can be preferred as per the preference of the programmer. |
| Coin Change Problem | O(nm) | O(nm) | Either | Both memoization and tabulation have the same time and space complexity. Either approach can be preferred as per the preference of the programmer. |
| Palindrome partitioning | O(n^3) | O(n^2) | Tabulation | Memoization has a higher time complexity than tabulation due to the recursive nature of the problem. The space complexity of memoization is higher than tabulation as it uses recursion stack. |
| Longest Increasing Subsequence | O(n^2) | O(n) | Tabulation | Memoization has higher time complexity than tabulation due to the recursive nature of the problem. The space complexity of memoization is higher than tabulation as it uses recursion stack. |
| Word break problem | O(n^3) | O(n^2) | Tabulation | Memoization has a higher time complexity than tabulation due to the recursive nature of the problem. The space complexity of memoization is higher than tabulation as it uses recursion stack. |
| Partition problem | O(n^2S) | O(n^2S) | Either | Both memoization and tabulation have the same time and space complexity. Either approach can be preferred as per the preference of the programmer. |
| Maximum bipartite matching | O(mn^2) | O(mn) | Tabulation | Memoization has a higher time complexity than tabulation due to the recursive nature of the problem. The space complexity of memoization is higher than tabulation as it uses recursion stack. |
| Bin packing problem | O(nW) | O(nW) | Either | Both memoization and tabulation have the same time and space complexity. Either approach can be preferred as per the preference of the programmer. |
| Edit Distance | O(mn) | O(mn) | Either | Both memoization and tabulation |