We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

570 questions
Filter by
Sorted by
Tagged with
28 views

### Can dynamic programming have n OPTimal subproblems?

I want to develop an algorithm which finds the optimal sequence of multiplications to multiply n matrices. For example, if we have: M1 x M2 x M3 x M4 x M5 x Mn The algorithm should place the optimal ...
40 views

### The path with the highest sum of weights

Mr. Katsaros owns a rectangular olive grove divided into 5 rows and 4 columns. He notes down the amount of olives (pounds) possibly obtainable from each of 20 square sections. The picking starts from ...
170 views

### Knapsack problem question

Based on this video, the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question. All the values on the first row (...
236 views

### Levenshtein distance algorithm with bits

I need to write a function that gets an array of bytes at the input and 2 integers (minDist and maxDist). The calculation algorithm understands this field as a bit sequence starting from the LSB (...
331 views

### How does matrix chain multiplication problem has an optimal substructure?

We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure? For eg. consider if ...
359 views

### Longest subsequence accepted by DFA (Dynamic Prog algorithm)

Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists. This problem has a runtime ...
98 views

### Dynamic Programming on bracketed sequences

I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a ...
52 views

### Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$:  N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
167 views

### Shortest Non-Subsequence String With Constant-Size Alphabet

Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (...
44 views

### Inserting values at maximal distance from current value

I have the following problem. Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules: If all elements equal 0,set A to 1 Next 1 should be set at ...
410 views

### Control of the combinatorial aspects of a dynamic programming solution

I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems. For this, I am looking at the canonical instance of the coin exchange problem: ...
407 views

### Find all the cumulative sums in a DAG

Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value. We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v). ...
61 views

### Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge

I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible ...
111 views

### Bottom-up algorithm to build subset of maximum weight

I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R ...
350 views

### How to “convert” a top-down solution to a bottom-up algorithm? [duplicate]

When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion. Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
675 views

### Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
713 views

### Dynamic Programming for a variant of the coin exchange problem

I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem: Given a value N, if we want to make change for N cents, and we have ...
127 views

### Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?

The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So ...
37 views

### Find minimum amount of feature combinations reproducing certain coloring of objects

PROBLEM Given a set of features $A = \{a_1, a_2, \ldots, a_m\}$. You have a set of objects $X = \{x_1, x_2, \ldots, x_n\}$ such that each object has certain combination of features. Some objects can ...
I am given an array $A$ having $n$ elements and an integer $k$. I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition: for ...