People who code: we want your input. Take the Survey

# Tag Info

## Hot answers tagged dynamic-programming

2

Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions. To answer your question, let's look at a simple example, change-making problem: Given a set of integer values of coins $C = \{c_1, …, ... 1 Suppose there are$c$types of balls, and there are$n_i$balls of type$i$. Let$S$be a set of types of balls. In how many ways can we choose balls so that only balls of type$S$appear, and at least one ball of type$i$appears for each$i \in S$? The answer is clearly $$\prod_{i \in S} (2^{n_i} - 1).$$ Taking$S = \{1,\ldots,c\}$, we get a solution to ... 1 Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function. For example, take the following problem: You are a cashier in a shop, and a customer gave you an$n\$-dollar bill (your country has bills of all kinds! very ...

1

Even though there is a backstory on the naming, as stated in the other answers, the term dynamic programming makes total sense. Dynamic means that something is changing. Programming means keeping a table (program or schedule), as it is implied to the term linear programming, too. Quoting CLRS “Programming” in this context refers to a tabular method, not to ...

Only top voted, non community-wiki answers of a minimum length are eligible