Note that there are two forms of dynamic programming. The first is a bottom-up programming, while the second is top-down programming (often known as memoization).
Try writing a recursive version, and then memoize it. Alternatively, write a top-down version of it
If the two last characters match, try 1 + LCS(m-1, n-1) If they do not match, try max(LCS(m-1,n), LCS(m, n-1)) If m == 0 or n == 0, return 0
O(mn)
if A[i] == A[j], try 1 + LPS(i-1, j-1), and use value if LPS returns True. also, try LPS(i-1, j) and LPS(i, j-1).
O(n^2) There is also an O(1) space algorithm.
Note: - There also exist an O(n) solution to palindromic subsequence, Manchester algorithm. - There is an interesting solution that uses LCS: https://www.techiedelight.com/implement-diff-utility/
O(n^2)
Time: O(nw)
Memo table is n (number of items) * W (maximum weight)
I believe there should be an O(W) table solution.
Memo table is O(n * sum)
Same as knapsack
Same as subset sum problem
Same as subset sum, but now form a k dimensional memo
For rod of length i, Try: price[j] + rodCut(i-j)