30 views

### Defining dynamic programming [duplicate]

Could we say that Dynamic programming is nothing but recursion + Memoization? Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, ...
• 143
2k views

• 613
701 views

### Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
• 227
1 vote
1k views

### What is the difference between dynamic programming and a mere caching?

I mean why should we use such epic buzzword when you can say: "cache your results!".
• 103
1 vote
2k views

### How can you determine what set of boxes will maximize nesting?

I'm trying to find a dynamic solution to the nesting boxes problem. You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
• 121
1 vote
1k views

### Understanding tables in Dynamic programming

I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where '.' Matches any single character. '*' Matches zero or more of the preceding ...
• 111
460 views

### Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
• 227
2k views

### How to balance parentheses/brackets in a string with minimum cost?

Given a word composed of opening and closing parentheses and brackets, we can do two operations: Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This ...
• 273
1 vote
581 views

### For dynamic programming problems, how do we know the subproblems will share subproblems?

So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when: ...
806 views

### How to "convert" a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
• 31