# Quick Note - Greedy Programming v/s Dynamic Programming

## Introduction

Generally speaking, there are two approaches to solving programming problems: greedy and dynamic. Greedy programming focuses on solving problems quickly, whereas dynamic programming focuses on solving problems efficiently.

## What is Greedy Method?

The greedy approach helps solve optimization problems. This strategy aims to achieve the maximum or minimum result possible. With a few terms, we can better understand the term problem.

Taking a greedy approach is the most straightforward approach. There is no algorithm involved, only a technique. We make the decision based only on current information, regardless of the impact in the future.

Using this method, you can determine if there is an optimal solution. When more than one solution satisfies the condition, it will be accepted as feasible, while only the best solution will be accepted among them.

## What is Dynamic Programming?

By using dynamic programming, we can reduce time complexity whenever we encounter a recursive form with identical inputs for repeated uses. Moreover, we can save the results of subproblems through recording.

With this minimal optimization, the technique can reduce the time complexity to a polynomial. For example, we could reduce the time complexity of the Fibonacci summation to linear if we record the answers.

As a result of dynamic programming, programmers can solve problems that consider the impact of variables and other factors. By breaking down a problem into manageable components and solving each separately, you can solve it more effectively.

By avoiding the overhead of calculating complex expressions and small ones simultaneously, dynamic programming allows programmers to solve complex problems with more than one variable in a predictable and analyzed way.

Optimization, regression analysis, and optimization are all situations where dynamic programming can be applied.

 Parameter Greedy Programming Dynamic Programming Basic Produces one decision sequence. Generates many possible decision sequences Reliability There is a lower degree of reliability with this method There is high reliability in this method Working Approach It prefers a top-down approach It prefers a Bottom-up approach Solutions Provide a specific set of feasible solutions. No particular set of feasible solutions exists. Efficiency It is more efficient than dynamic methods A less efficient method than greedy methods Example Fractional knapsack, shortest path 0/1 Knapsack