# Tagged Questions

Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.

19 views

### Optimal Apple Eating Strategy

You hate apples. As a result, you have angered the apple king and are being punished. You will have to eat $n$ apples before the apple king is willing to let you leave. The apples are marked from $1$ ...
13 views

### Pontryagin's maximum principle

So I've been doing some optimal control theory lately. It's really interesting but I've spent the whole day trying to wrap my head around pontryagin's maximum principle. There's a lot of mathematical ...
44 views

### Maximum Coin Changes That Does Not Add To a Dollar

What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic ...
14 views

### How is the system equation formulated? [Resource Allocation Problem]

I do not find how the following system equation is formulated. The following example is about the Deterministic Continuous-Time Optimal Control chapter. We are considering a continuous-time dynamic ...
18 views

### Minimum number of Coins needed to make change?

I was trying to solve the one particular problem and I ended up reading this. I read this question Above link states the problem of changing the amount when coins are given in infinite amount. ...
49 views

### Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
90 views

### Given a population of fish with exponential growth, what is the optimal strategy for fishing?

Suppose we have a population of fish, say $10000$, with an exponential growth each year of $30\%$. If we want to collect as many fish as possible in, say 10 years, a natural question to ask is: ...
24 views

### concise book on MDPs with stress on solving them using DP

What is a good book for MDP with a stress on solving them using DP? However, the book should stress on the theorems and proofs and make a case for why DP is the most popular tool to solve MDPs. I am ...
55 views

### $L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
16 views

### Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
30 views

### How to handle Finite-state-machine with correlated inputs?

My system can be represented by the following state-diagram. where each arch represents Input/Output when a transition is made from one state to the other. The inputs to this FSM are correlated. ...
19 views

### Dynamic Programming problem with extremely high dimension over 1000

I am dealing with a dynamic programming problem with extremely high dimension. Currently, I know some methods like Smolyak algorithm and Adaptive sparse grid method. They can solve problem with ...
79 views

### Help me to solve $\overline{abc} \cdot d +\overline{ef}\cdot g + h \cdot i = 2010$

The problem is: $$(a \cdot 100 + b \cdot 10 + c ) \cdot d + (10\cdot e + f ) \cdot g + h \cdot i = 2010$$ and $$\{a, b, c, d, e, f, g, h, i\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}.$$(not allowed to repeat). ...
31 views

### Programming Bifurcation analysis

Next year I'm going to do my final project for graduation. I've been assigned to search and study some biomathematical models with bifurcation theory and numerical bifurcation analysis. I'm thinking ...
28 views

81 views

### Converting Java Code to Mathematic formula

I have algorithm , but I don't know how to convert it to mathematic formula. ...
Let $\beta$ be a fixed constant (it isn't specified that $\beta <1$, but assuming it is okay if it is necessary), and $u$ be some function from $W\to \mathbb{R}$. Let there be two discrete states, ...
The original problem: http://codeforces.com/blog/entry/20508 581F — Zublicanes and Mumocrates, I want to prove that the time complexity is $O(n^2)$. Suppose we have a tree, how to prove that \$\sum_{v=...