# 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.

606 questions
Filter by
Sorted by
Tagged with
20 views

307 views

### Number of sequences that satisfy the absolute difference condition

Let $x_0 =0$ and let $x_1,.....x_{10}$ satisfy that $|x_i - x_{i-1}|$ = 1 for 1≤i≤10 and $x_{10} = 4$ . How many such sequences are there satisfying these conditions? I tried to calculate it by ...
• 31
126 views

### Is there a closed form for the Josephus Problem on a line?

Consider the following variation of the famous Josephus problem: The numbers 1 through $n$ are lined up. Each round, every $k$th number is eliminated, starting from the first one (so the numbers in ...
1 vote
37 views

### differential dynamic programming : Intuition, key idea and difference from dynamic programming

I cam across 'Differential Dynamic Programming' in a course on Optimal Control. In this course , we were introduced to Dynamic Programming prior to DDP. I went through the Wikipedia Post on ...
• 11
1 vote
49 views

### Proof that the least number of steps to some value $i$ if you can only travel in increasing powers of 2, is never done by overshooting $2i$

The problem: This question is inspired by a proof of correctness for the algorithms question that can be found here To summarize, starting from $0$, you want to get to some target $i > 0$. You may ...
• 455
61 views

### Contest problem(Combinatorics//maybe DP)

Problem : There are n people in a party. Each person can either join dance as a single individual or as a pair with any other. Find the number of different ways in which all n people can join the ...
• 67
110 views

Let $N = \{1, 2, \ldots, n\}$ denote a set of items, $w \in \mathbb{R}_{++}^N$ a vector of weights, $c > 0$ a constant and $x \in \{0, 1\}^N$ a decision variable. The objective is to minimally ...
• 771
95 views

### Find the number of subsets of n chairs in a circle containing at least three adjacent chairs

Find the number of subsets of $n$ chairs in a circle containing at least three adjacent chairs. I know that the answer for $n=10$ is $581$, and the solution is here for instance. I'm not sure if it's ...
• 293
50 views

### What is the probability that no 2 adjacent bits are 1?

Given a binary vector, what is the probability that no 2 adjacent bits are 1? Let's say the probability for value 1 is p. I ...
• 47
1 vote
59 views

### Optimality of greedy knapsack algorithm.

Consider the array of tuples $(t_i, p_i, q_i)$, where $t_i \in \{0, 1\}$ means type of order ($0$ for sell and $1$ for buy), $p_i$ is price of order and $q_i \in (0, 1)$ is volume of the order. Assume ...
• 6,458
93 views

### ILP constraints for connectivity in a matrix

I'm trying to use ILP to solve the following problem: A series of connected nodes are provided. For the example below, $a$ is only connected to $b$, $b$ is connected to both $a$ and $c$, $c$ is ...
• 11
91 views

### Consequence of Dvoretzky Stochastic Approximation Theorem

I am having some problems trying to apply Dvoretzky Stochastic Approximation Theorem to one Lemma used in a paper I found about the proof of convergence of some reinforcement learning temporal ...
• 41
114 views

### Why are the costate equations solved backwards in time?

I'm trying to find an optimal control to a simple nonlinear SIR model. I am trying to undersand the Pontryagin minimum principle but I don't understand why the costate equations must be solved ...
• 148
1 vote
41 views

• 15