dynamic programming - Is a Greedy problem a recursive algorithm without overlapping sub-problems?

Question

I am new to Data Structures and Algorithms and was wondering about Greedy approach and Dynamic Programming(DP) approach. After a long struggle I seem to sort of grasp the step by step approach to solving a DP problem. However I seem to mis-understand problems which require a greedy approach to DP problems. By definition Greedy approach means we choose the best solution at every step and DP has overlapping sub problems.

The root of my confusion is that I solve a DP problem recursively first then look for overlapping sub-problems and use memoisation to improve the solution.

My question is that can I call recursive solution for a DP problem without memoisation a Greedy Solution. For example while solving the popular Knapsack problem we either choose to add an item to the Knapsack or not. We then choose the best possible outcome at every step. Now the Knapsack problem has overlapping sub problems and is a DP Problem. But my question is what if it didn't had overlapping sub problems. Can we call the recursive approach without memoisation a greedy approach for Knapsack problem?

Please help me out as I am a complete beginner and this has been bugging me for a while.

Thanks!

Answer 1

From Your question, I understood that you are having confusion between DP and the Greedy approach.

DP--Taking intuition about Dp, actually Dp is the approach in which we check for all possible solutions which can be a contestant for the actual solution, we select anyone from it. But the thing that makes Dp different is the overlapping subproblem. Now, what is the overlapping subproblem - suppose we have to calculate the sum of all numbers from 1 to 7, we find the answer by doing 1+2+3+4+5+6+7 and store that answer, Now we have to calculate sum from 1 to 10, now what we will do 10+9+8+ans(7) this means we have reduced our efforts of doing the same thing which we have done before. This has drastically reduced our time. So actually this is DP. Whether we apply recursion or iterative we have to store past results. So actually saying about DP, it is recursion + remembering the past answers.

Now telling about Greedy - In greedy, we don't check for every possibility, we find the answer on the basis of the previously found optimal solution, but don't check about every possibility.

This concept will get more and more clear once you will solve a sufficient amount of questions on both topics.