Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [dynamic-programming]

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

-2
votes
0answers
13 views

Range queries on million number array

I have an array of million numbers. I want to find the maximum number in range queries wherein each query I am given left and right index. What is the effective way of doing that?
3
votes
2answers
73 views

Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
1answer
27 views

Trying to understand the question(well spaced points ?) better

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
2
votes
1answer
48 views

Lexicographically smallest down-right path in matrix

Here is the problem which I thought was simple dynamic programming, which is however not the case. Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
1
vote
1answer
40 views

Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer). You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
1
vote
2answers
77 views

Doubt over the index value used in dynamic programming

I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string. After seeing the brute force(recursive solution), I went ...
2
votes
2answers
32 views

Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
1
vote
1answer
55 views

Maximum product of contiguous subsequence over $\mathbb{R}$

For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here). Let us first show how to solve the ...
0
votes
1answer
42 views

Dynamic Programming Problem on Tree

Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
1
vote
1answer
64 views

How does dynamic programming work in this example(generating the tables )

For example, a sequence has the defined growth property: if it is a sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such that: $a_{1}=1.$ $a_{n+1} \leq$ Max$_{1\leq i \...
1
vote
0answers
31 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 ...
0
votes
0answers
28 views

findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
-1
votes
1answer
86 views

Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ? Problem : There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to ...
1
vote
1answer
32 views

Computing number of ways to make change

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
2
votes
1answer
132 views

Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Let PARTITION-INTO-THREE-SETS be defined as following: Input: Positive integers $a_1, ..., a_n$ Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
1
vote
1answer
32 views

Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
0
votes
0answers
18 views

Value iteration in MDP - updating each state once per inner loop?

In value iteration algorithm we update the utility of all possible states ("for each state update its new utility"). After we've updated all states we check to see if the delta is smaller than some ...
1
vote
1answer
23 views

What Are the Ideas Behind Variations of the Coin Change Problem?

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for ...
1
vote
0answers
49 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
1answer
49 views

Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?

I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop. Is this reasoning correct or is there more to it?
1
vote
0answers
23 views

Count paths in matrix that visit each number exactly once

Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$. We want to count the number of paths that start ...
2
votes
2answers
59 views

Technique for converting recursive algorithm to DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
2
votes
4answers
68 views

Prooving by Pigeonhole principle

I've been given a question to solve: ...
1
vote
2answers
45 views

set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
0answers
68 views

Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows A = [3,4,5,6] B = [9,8,3] Now, I have ...
2
votes
1answer
32 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
1
vote
1answer
44 views

Number of contiguous subsequences summing to a given target

I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$. For ...
0
votes
0answers
20 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
2
votes
2answers
77 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
2
votes
1answer
83 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
1
vote
1answer
80 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
11
votes
1answer
192 views

Word factorization in $O(n^2 \log n)$ time

Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a ...
1
vote
1answer
58 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
2
votes
0answers
23 views

What are the pros and cons of context-oriented programming (COP)?

I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
1
vote
1answer
51 views

How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
0
votes
1answer
40 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
0
votes
0answers
56 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
46 views

What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
2
votes
3answers
62 views

Algorithm to find smallest number divisible by N with sum of digits as N

Problem: Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$. For example: $n = 1$, answer is $1$ $n = 10$, answer is $190$ There is some dynamic programming ...
1
vote
1answer
56 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
1answer
38 views

Sum of zero nim sum series

The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
1
vote
0answers
42 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 ...
2
votes
0answers
61 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
46 views

Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing. I am working on the following problem: Suppose you are consulting ...
1
vote
1answer
92 views

Gerrymandering Problem: Variant on Set Partitioning

I was recently helping a friend with homework from a dynamic programming class, and this was the question: Given a set of n precincts P1 ,... Pn , each containing m votes, with <...
2
votes
0answers
39 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
0
votes
0answers
20 views

Given graph with N nodes colored in K colors, count paths visiting each color exactly once

Let's say we have given graph of at most $N = 400$ nodes, and each node is colored in one of $K = 21$ colors. We need to count paths of length $K$, such that each node on the path is in one of the $K$ ...
2
votes
1answer
46 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
1
vote
3answers
151 views

Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
0
votes
1answer
118 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....