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
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
22 views

Dynamic programming for subsequence metric

Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $...
1
vote
1answer
182 views

longest palindromic subsequence / substring and dynamic programming

The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-...
1
vote
0answers
61 views

Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $f(x,n)$, ...
1
vote
0answers
39 views

Weighted Activity Selection Problem with allowing shifting starting time

I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists. In my case, I am allowed to ...
1
vote
0answers
21 views

Dancing Links use in tiling problems

I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but ...
1
vote
0answers
45 views

How does the asterisk (*) work in the wildcard matching problem?

This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
1
vote
0answers
28 views

Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...
1
vote
0answers
38 views

Text Segmentation Problem give Word Frequencies in a Universe

Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I ...
1
vote
0answers
141 views

Is MCTS an appropriate method for this problem size (large action/state space)?

I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
1
vote
0answers
137 views

Parenthesizing a product using dynamic programming

Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$. Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon ...
1
vote
0answers
687 views

How can I find worst time complexity for a Regular Expression problem?

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution? One way is to perhaps use The Master Method for ...
1
vote
0answers
1k views

Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence. ...
1
vote
0answers
84 views

Comparison of time-dependent traveling salesman heuristics

I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time. There are a wide range of possible ways to ...
1
vote
0answers
309 views

A knapsack problem with variable knapsack size

I've come across this problem and I can't find a decent DP solution for it. Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), ...
1
vote
0answers
76 views

Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for ...
1
vote
1answer
913 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 ...
1
vote
0answers
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 ...
1
vote
0answers
515 views

Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) <...
1
vote
0answers
57 views

Given a Tree decomposition, How to find the tree decomposition of its subgraph?

You are given a tree decomposition of a large graph with not so small bounded tree-width. Suppose now you need to solve a dynamic programming problem inside a subgraph and does not have time to do ...
1
vote
0answers
284 views

A variant of the house robber problem

I came across a modification of the classic house robber problem where the robber cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house. The modified ...
1
vote
0answers
52 views

Optimal Strategy for Number Reducing Game

There are $n \in \mathbb{N}$ towers, each with a height and a value. Let the positive integers $h_1, h_2, \dots, h_n$ be the heights and $v_1, v_2, \dots, v_n$ be the values, respectively. Two players ...
1
vote
0answers
240 views

Waterman-Smith-Beyer Algorithm

I am having trouble understanding the affine gap penalty in the following example - Waterman-Smith-Beyer Algorithm: \begin{align*} D_{0,0} &= 0\\ D_{0,j} &= g(j)\\ D_{i,0} &= g(i)\\ \...
1
vote
0answers
153 views

Edge coloring optimization using dynamic programming

The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than ...
1
vote
0answers
125 views

proving that local sequence alignment can be done in linear space

according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all ...
1
vote
0answers
251 views

Find equal length subsequences with maximum difference of sums, for given maximum subsequence length

The problem is the following. Suppose we have a sequence of n non-negative numbers, each element with index i having its own ...
1
vote
0answers
80 views

Count all possible 2-3-monotone sequences

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as: $s_i < s_{i+2}$, for $1 \leq i \leq N-2$ $s_i < s_{i+3}$, for $1 \leq i \leq N-3$ $s_i \in \{1,\dots, N\}$ Given $N$...
1
vote
0answers
799 views

Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
1
vote
0answers
907 views

Josephus Problem - A faster Solution

I came through Josephus problem a little while ago. Problem is stated as follows : "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
1
vote
0answers
469 views

Solving a Knapsack problem with a special structure

I have a set of $N$ items to fill a knapsack with maximum capacity $W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following: max $\...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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$...
1
vote
0answers
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: ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 = ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
28 views

Multiple Optimal Solutions in Dynamic Programming

In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the ...
0
votes
0answers
29 views

Matrix chain multiplication using dynamic programming

Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem : The table for min. cost is shown below : Edit : Reference https://www.radford.edu/~nokie/...