Comment expliquer la programmation dynamique à un débutant en algorithmique ?

I find dynamic programming to be a fairly intuitive pattern in terms of managing time/resource efficiency. Simply put, it is storing and looking up previously completed costly calculations. In other words it is a trade-off between memory and compute/time.

Dynamic programming is - calculated once, and used multiple times. Imagine how inefficient it would be if I asked you to calculate the same thing again and again if it has already been calculated already. And that's where the problem needs to have a pattern where it can be broken into overlapping subproblems. And so you just calculate the subproblem once and then use its calculated value directly wherever it is being used later.

Basically all the subproblems are dependent on each other in Dynamic Programming. You also divide a problem into smaller problems in Divide and Conquer strategy, however, subproblems are independent in that case, like Binary Search where both halves are independent, you can go to any half. In Dynamic programming you have to solve first subproblem and store in a table in order to solve the next subproblem

"Dynamic Programming" can be thought of as "Divide and Conquer" which is a famous strategy used when it comes to solving problems. Similar to Divide and Conquer, we apply Dynamic Programming to problems that can be DIVIDED into multiple sub-problems, solving/CONQUERING all of them would thereby solve the entire problem

Dynamic programming is a powerful concept in the field of algorithms that are often used to solve optimization problems. At its core, dynamic programming involves breaking down a complex problem into simpler, overlapping subproblems and solving each subproblem only once, storing the solutions to subproblems in a table to avoid redundant computations. The key idea is to build up to the solution of the original problem by solving increasingly larger subproblems in a systematic manner. This approach is particularly useful for problems with overlapping substructures, where the same subproblems are solved multiple times.

The Fibonacci sequence is a famous example where dynamic programming can be very effective. In the series, each number is the sum of the two preceding ones, starting with 0 and 1. So, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13 and so on. When we calculate a Fibonacci number, say F(5), we need F(4) and F(3). To get F(4), we need F(3) and F(2). Notice how F(3) is needed multiple times. In a naive solution, we would be calculating F(3), F(2), F(1), etc., multiple times, leading to a lot of repetition. Dynamic programming combats recalculation with memoization. By storing previously calculated values, we can reduce recalculation, drastically reducing time complexity and boosting efficiency, making it ideal for problems with repetitive tasks.

Going forward with the "Divide and Conquer" mental model, when we come across problems that can be divided into smaller problems and can be individually conquered, then we shall use Dynamic Programming. This check is actually quite famous when it comes to algorithmic problems that can be solved using Dynamic Programming. It's called "Optimal Substructure and Overlapping Sub Problems" which quite literally means that the main problem can be broken down into sub-problems that can then be optimally solved to get the right answer

Here are some situations in which dynamic programming can be applied effectively : 1. String and Sequence Matching: Dynamic programming is commonly used for problems involving string matching, sequence alignment, and edit distance calculations. The Needleman-Wunsch algorithm for global sequence alignment and the Smith-Waterman algorithm for local sequence alignment are examples. 2. Shortest Path Problems: Problems involving finding the shortest path to reach a certain state or goal often lend themselves to dynamic programming. This includes problems like the Floyd-Warshall algorithm for all pairs shortest paths or Dijkstra's algorithm. 3. Resource Allocation Problems: Problems that involve allocating limited resources in an optimal way.

In the context of the Traveling Salesman Problem, dynamic programming efficiently solves it by breaking it down into overlapping subproblems. It uses memoization to store the shortest paths for subsets of cities, significantly reducing computation compared to exhaustive search. This approach transforms an otherwise exponential problem into a more manageable task, demonstrating dynamic programming's effectiveness in optimizing complex combinatorial challenges.

Dynamic programming is most effective when a problem has two key properties: Fibonacci Series: Calculating Fibonacci numbers using dynamic programming significantly reduces redundant calculations by storing the results of previously solved subproblems. Shortest Path Problems: Algorithms like Dijkstra's or Floyd-Warshall's can be optimized using dynamic programming when finding the shortest path in a graph. Knapsack Problem: When trying to optimize the selection of items to include in a knapsack given their values and weights, dynamic programming can efficiently find the optimal combination. etc

When you find out that the main problem that you are dealing with can be solved by breaking it down into multiple subproblems. You'll more often than not find out that there lies a relationship between how these sub-problems are connected together. This relationship that exists between the sub-problems is called a "recurrence relation". Simply because it keeps re-occurring between every sub-problem. Practically, you have a solution space ( Array / 2D Matrix ) to store the sub-problem solutions and by the time you reach the end of your solution space, you would have solved the entire problem.

Defining the subproblems and finding the recurrence relation are the most crucial steps. For many problems, there are multiple definitions or recurrences which are correct, each expressing a different perspective on the problem. Some may be more efficient or intuitive than others.

Often, the solution sought using dynamic programming represents an optimum, according to a given metric. In such cases, it is necessary to prove mathematically that the recurrence formula results in the optimum for the combined problem, given the optima for the subproblems.

Dijkstra's algorithm to find single source shortest path, Floyd Warshals algo to find all pair shortest path, Matrix chain multiplication are another examples of DP.

Dynamic Programming need not be seen from a Computer Science perspective. Making a sandwich is a problem that can be solved using Dynamic Programming. Each component of the sandwich is a sub-problem. If you're able to optimally solve these sub-problems and use them together to get your entire sandwich. Finding the shortest route to go to your concert is a problem solved by Dynamic Programming ( Travelling Salesman ) Packing your luggage when you go to your next vacation is a problem solved by Dynamic Programming ( Knapsack )

Fibonacci even though an example for dynamic programming it does not really highlight the efficiency of Dynamic Programming. Knapsack on the other hand is kind of hello world for Dynamic programming.

In addition to the examples mentioned, the Dynamic Time Warping (DTW) algorithm provides a relatively simple application through an approach that can visually show the time warping between two structurally similar sequences (traditionally signals). We can also expand upon the longest common subsequence problem with reference to string matching or the number of edits made to one string/sequence to produce the other, know as the Levenshtein distance. With slight modifications to this algorithm we can store information on which subsequences/characters have been added, edited, removed, or remain unchanged. Keen eyes may note this is the basis of the diff algorithms used by git/svn to mark revision changes across file versions.

One of the way to use dynamic recursive programming it is creating the xml to dict (JSON) converter with python. This code could be provided with just some strings, but will work properly as you need

A few pointers improve dynamic programming's efficacy. First, think about dividing the issue into more manageable, smaller subissues. To see the structure and find overlapping subproblems and the best substructure, draw the recursion tree and the associated table or array. To maximize efficiency, store and reuse subproblem answers using memoization or tabulation approaches. Moreover, simplify storage by using only relevant portions of the table or array to increase space complexity. All of these tactics work together to make the implementation of dynamic programming more simplified and effective.

The existing tip is merely a reiteration of the solution procedure. A better tip is to look for similarities between the task at hand and the classic problems given in the examples, as their solutions are well understood. Moreover, programming competitions and olympiads (such as USACO, ACM, etc.) often present challenges meant to be solved using dynamic programming. These constitute excellent practice material for training and getting into the mindset of dynamic programming.

Dynamic programming is a powerful optimization technique often used in computer science and algorithmic problem-solving. One fundamental concept in dynamic programming is breaking down a complex problem into smaller, overlapping subproblems and solving each subproblem only once, storing the results to avoid redundant computations. Memoization, or storing previously computed results in a table, is a key aspect of dynamic programming that contributes to its efficiency. This technique is particularly beneficial in scenarios where the same subproblems are encountered multiple times in the process of solving the overall problem.

What I've found most helpful is to practice formulating a recurrence for as many different problems as possible. Try and find multiple ways to formulate the same problem, and look at the difference in the running times which result.

Memory requirements can be reduced after identifying the number of subproblems that need to be considered to solve the one at hand. Often, only one or two levels in the hierarchical tree nedd to be cached, while discarding the rest. In other cases, extra computation can be traded for memory. Dependi g on the algorithmic complexity, this can be beneficial, especially on hardware with high memory latency and an abundance of computing power, such as GPUs.

Dynamic programming is a powerful algorithmic technique with its own set of trade-offs and challenges. One key advantage is its ability to efficiently solve problems with overlapping subproblems by storing and reusing solutions to subproblems, which can lead to significant time savings. However, this efficiency comes at the cost of increased space complexity due to the storage of solutions in a table or memoization array. The trade-off between time and space complexity is a critical consideration, particularly when dealing with problems of varying sizes.

Sometimes it is difficult to apply 2dimensional DP or DP on graph based problems. Also sometimes using top-down instead of bottom-up or vice versa is much easier than the other.