![New sister in law causing family drama [closed]](https://cdn.sstatic.net/Sites/interpersonal/Img/apple-touch-icon@2.png?v=17e836faa592)
![Internal server error [closed]](https://cdn.sstatic.net/Sites/softwareengineering/Img/apple-touch-icon@2.png?v=1ef7363febba)
Dynamic Programming
Every time I've approached learning algorithms, I've come across the phrase "Dynamic Programming". Which sounds complicated, but it's interesting the book I'm reading just basically says "Dynamic Programming is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems, then you can cache those results for future recursive calls) Which makes it sound pretty easy. I mean, I know what Recursion is, though, maybe because I didn't learn recursion until much later in my programming journey, but it seems much harder to read, and much less intuitive to me than just using loops. If I squint I can see why recursion might be intuitive for some, just not for me. The most common recursive example, the fibonnaci sequence, always seemed bananas to me. Why do all that work, just add numbers. Maybe this is why Question 55 on LeetCode, Jump Game seems bananas to address as a dynamic programming problem. Sure you can go to all that work, but my observation is that you can solve it with just a single loop, by treating each stop as a gas station. Start at the first step, and decrement one each time. If you pass an index that is bigger than your current number, set your "gas level" to that number. See if you can make it to the end. But I'll play the game. It seems like the base case for Jump Game, is that you check every spot against every other spot to see if that spot can make it to the end. Then the real optimization for number to is you can memo certain spots, because in the original example you're checking the same spot multiple times. This reduces a 2^N to a N^2 (Apparently the editorial for Question 55 as of Jan 22 2025 has the wrong example 3 Approach 3: Dynamic Programming Bottom-up? It looks like it comes from the stock trading example.
Every time I've approached learning algorithms, I've come across the phrase "Dynamic Programming". Which sounds complicated, but it's interesting the book I'm reading just basically says "Dynamic Programming is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems, then you can cache those results for future recursive calls)
Which makes it sound pretty easy. I mean, I know what Recursion is, though, maybe because I didn't learn recursion until much later in my programming journey, but it seems much harder to read, and much less intuitive to me than just using loops. If I squint I can see why recursion might be intuitive for some, just not for me. The most common recursive example, the fibonnaci sequence, always seemed bananas to me. Why do all that work, just add numbers.
Maybe this is why Question 55 on LeetCode, Jump Game seems bananas to address as a dynamic programming problem. Sure you can go to all that work, but my observation is that you can solve it with just a single loop, by treating each stop as a gas station. Start at the first step, and decrement one each time. If you pass an index that is bigger than your current number, set your "gas level" to that number. See if you can make it to the end.
But I'll play the game. It seems like the base case for Jump Game, is that you check every spot against every other spot to see if that spot can make it to the end. Then the real optimization for number to is you can memo certain spots, because in the original example you're checking the same spot multiple times. This reduces a 2^N to a N^2 (Apparently the editorial for Question 55 as of Jan 22 2025 has the wrong example 3 Approach 3: Dynamic Programming Bottom-up? It looks like it comes from the stock trading example.
What's Your Reaction?
