# Questions tagged [dynamic-programming]

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.

442 questions
Filter by
Sorted by
Tagged with
50 views

### Stabilizing controls in linear quadratic regulator

I am studying a linear quadratic control problem with discounting. For $\gamma \in (0,1)$, $Q \succeq 0$ and $R \succ 0$ and linear dynamics $s_{t+1}=As_t + B a_t$, let the total cost starting in ...
41 views

### Dynamic programming with less decision variables than states

I'm trying to solve a dynamic programming problem with $n$ (continuous) state variables and only $1$ (continuous) decision variable, which affects all the states. For $n=1$ this is a standard problem ...
27 views

### Generate all possible sums of $N$ (with repetitions) [closed]

I want to get all possible sums out of numbers: $1, 3, 4$ that are equal to a given number $N$. There are some restriction: sequence order is important and algorithm cannot use recursion. For example, ...
18 views

### Dynamic programming: find possible sums of given digits to reach given sum

Maybe anyone has idea how to solve this problem using dynamic programming: I have a natural number. Let’s name it n. Then, have digits: 1, 3, 4. I have to find all possible sums (with repetitives) of ...
19 views

### How to convert a function to separable form?

I am reading the book, "Introduction to dynamic programming", by Leon Cooper. In the first chapter they define a separable function as A separable function is one in which the function consists of ...
10 views

26 views

### Knapsack Problem (Optimal solution through Dynamic Programming): When limit is less than the nth (or ith) weight and purpose of max?

I am trying to understand the knapsack problem from the book: Algorithm Design Equation (1) deals only with the case when nth item is too big. But why in the “Otherwise” case we have included the ...
26 views

### Knapsack Problem using Dynamic Programming: Mathematical Equation

I am trying to understand the knapsack problem from the book: Algorithm Design I can’t understand the following equation. This provides solution to knapsack problem in the context of Dynamic ...
23 views

### Optimal substructure of rod cutting?

How do you show the optimal substructure of the rod cutting problem(defined as in https://cs.stackexchange.com/q/97674). I am trying to follow the guideline steps So suppose someone told us one of ...
15 views

### Optimal strategy for tossing three dependent coins

Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$. The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ ...
46 views

### Probability of getting certain number of points

A one on one basketball tournament is happening in your community. Each game has a point system. 3 points for a win, 1 point for a tie, and 0 points for a loss. You have a 50% chance on winning, 40%...
Given is a sequence of "A-points" $A_1,\dots,A_k$ on a grid, and we have to give an optimal path, i.e. a sequence of points $P_1,\dots,P_k$ such that $P_i$ and $P_{i+1}$ share a row or column, and \$\...