Questions tagged [dynamic-programming]

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

155 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
19 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
73 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
36 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
16 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
37 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
27 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
2answers
112 views

Given matrix, count paths visiting each number exactly once

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
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
128 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
79 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
289 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
1answer
61 views

Optimizing the problem

I have a recurrence relation: $$f(a,b) = \begin{cases} 1 & (a,b) = (0, 0)\\ 1 & (a,b) = (a, 0)\\ 0 & (a,b) = (0, b)\\ 2a & (a,b) = (a,1)\\ f(a-1,b) + f(a-2, b-1) + f(a-1,b-1)...
1
vote
2answers
165 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
130 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
539 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
281 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
74 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
768 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
457 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
53 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
270 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
48 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
232 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
143 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
118 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
246 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
725 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
850 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
450 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
40 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
66 views

Dynamic programming: maximize the number of things to be bought

For example, for a product, we have a list of the number of products you buy and the corresponding price you pay with this number of products: number = {1, 5, 8, 12} price = {0.5, 2, 3, 3.6} (i.e. ...
1
vote
0answers
349 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
78 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
829 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
642 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
0answers
7 views

Algebraic Dynamic Programming breakdown of a simple problem (e.g. climbing staircase)

I found recently about Algebraic Dynamic Programming. As I understand, it's a formalization that immensely simplifies developing solutions for DP problems. I spent a few days trying to grok it, to no ...
0
votes
1answer
57 views

Dynamic programming

Got a question and can't manage to find an answer, so help will be appreciated. I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
0
votes
0answers
33 views

What are some variants of the rod cutting problem?

I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
0
votes
0answers
39 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
0
votes
0answers
29 views

Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
0
votes
0answers
86 views

Minimizing the distance from a set of nodes in a tree

We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
0
votes
0answers
36 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)$, ...
0
votes
0answers
21 views

Dynamic programming algorithm with an O(n) performance that will give the optimal solution

I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...