# Questions tagged [dynamic-programming]

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

163 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
36 views

### Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
55 views

### Optimal ordering - Dynamic programming on subsets

We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$. The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
22 views

93 views

### Possible Distribution of coins

We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$. The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
321 views

### Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))

So this is a question within a bigger question for which I've reduced to this so far: If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
202 views

### FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
137 views

41 views

### Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
350 views

### Finding max average value subrectangle at least a certain size in a 2-d sparse array

So Kadane's dynamic programming solution for finding the maximum sum contiguous subinterval in a 1-d array runs in linear time, and can be adapted to give a best-known $O(m^2n)$ time solution to find ...
79 views

### Dynamic Programming - Seemingly unnecessary recursion?

I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of ...
67 views

### Algorithm for keeping the Maximum and allowing Splits of Strings/sequences

The problem is as follows: Given $k$ strings of size $n$, propose a data structure to support the following operations: Return the maximum of a string. Given an index $i$, and $2$ strings $a$ and $b$...
2k views

### Traveling Salesman with Held and Karp Algorithm

I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP. I have implemented it with bitmask, and it's something like this: ...
830 views

### Fast algorithm for finding a minimum cost path through points in the plane

Consider the following problem: There are $n$ points in the plane. Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way ...
644 views

### Writing a program to find the optimal reward for a 2-armed Bernoulli bandit

(It might be useful to refer to page 9 of Multi-Armed Bandit Allocation Indices by Gittins, Glazebrook and Weber if you have it, because there explanation will be much better than mine.) I'm trying ...
411 views

### Recursive relation help for dynamic programming 2D plane algorithm

Consider a straight highway in the plane which can be modelled by a horizontal strip in the plane. A finite set T of targets are located on the highway, and a finite set S of wireless sensors are ...
49 views

### Dynamic Program for Tree based question

You are given a tree T where every node i has weight wi ≥ 0. Design a polynomial time algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the following picture wa = ...
20 views

### Linear Partition problem (Dynamic Programming) in a circular array

I am practicing algorithms for the last couple of days and I came across this question, the gist of which is: Given apples and oranges arranged in a circle indexed form 1 to n , where n is an odd ...
24 views

### Alternate Knapsack Implementation

I came across a question that requires an alternate implementation converse to the normal Knapsack which is based on a 0-1 logic of considering whether or not to consider an item for the optimal ...
23 views

### How to trace Subset from Boolean DP table in the Subset Sum Problem

I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ...
13 views

### Variant of box stacking algoritm

I'm trying to solve this problem which I believe is a variant of box stacking algorithm. Problem : Suppose I have n boxes each with height h, width w, length l. Now if one box can fit inside another ...
29 views

### Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements

So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if ...