Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
728
questions
1
vote
1answer
30 views
How to create a subset with a given length and mean?
I have a set of numbers $P=\{p_1,\dotsc,p_{|P|}\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\...
0
votes
1answer
46 views
What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any ...
1
vote
1answer
22 views
How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?
Theorem 15.1 (Optimal Substructure of an LCS)
Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS.
If $x_m = y_n$, then $z_k ...
1
vote
1answer
23 views
Finding optimal separating value
Problem description
We are given two sorted arrays of even numbers: A and B.
Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
2
votes
1answer
47 views
Question on an Algorithm for Longest Increasing Subsequence
I have been reading this paper: https://arxiv.org/abs/2011.10874
This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
0
votes
1answer
83 views
the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs
Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair.
My attempt
...
1
vote
1answer
38 views
Minimum number of swaps to make two arrays strictly increasing
I'm trying to understand the solution of the following problem (LC 801):
Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B ...
0
votes
1answer
33 views
Longest path on a full tree
Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves.
I was thinking I could use some sort of BFS. Because I'm looking for maximum ...
0
votes
2answers
112 views
Find the minimum subset of a set of numbers with product divisible by a given integer
The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
...
1
vote
1answer
107 views
Why is backtracking a necessary step in the Maze problem?
The problem I am working on is specifically this:
A Maze is given as N*N binary matrix of blocks where source block is
the upper left most block i.e., maze[0][0] and destination block is
lower ...
0
votes
0answers
40 views
Dynamic programming algorithm to find largest triangle in binary square matrix where elements equal “1”
I'm struck how to find DP recurrence for:
You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1,
q >= 1, L >= 1, p+L >= n+1, and q+L >= n+...
-1
votes
0answers
54 views
Dynamic programming substring problem with 4 characters
You start with a string made up of 4 characters: A, B, C, and D. The string can be at most 10^5 characters long.
You edit the string in this manner:
Split the string between two consecutive ...
0
votes
1answer
30 views
Calculate the sum of all sub-arrays with given indices
I am new to Algorithms and Competitive Coding. I have a problem as follow:
For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic ...
2
votes
3answers
91 views
how does the shap algorithm work in polynomial time?
I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based ...
2
votes
1answer
50 views
Matrix chain multiplication recurrence and its solution
We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.
In the classical matrix chain multiplication problem, we wish to minimize the total ...
0
votes
0answers
28 views
0/1 Knapsack problem. How does the total weight does not exceed the limit?
I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing.
On the left is the [val,weight] and on the ...
0
votes
1answer
84 views
Count the possible plans for nurses
I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:
The director of a hospital want to schedule a working plan for a nurse
in a given period of N ...
0
votes
0answers
16 views
Write recurrence for cost minimization
So I am trying to find the recurrence for this problem but I feel like it is missing something.
An ice cream shop is looking to minimize their operation costs, under the given constraints:
They are ...
1
vote
2answers
39 views
Two-Sum - Range Allowance Algorithm Design
🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity?
Optimize for runtime over memory complexity.
...
2
votes
1answer
27 views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
2
votes
0answers
40 views
Relationship between dynamic programming and reinforcement learning
I wasn't sure whether to post this here or in the ai stack exchange - please let me know if i need to move my post elsewhere)
I have been learning about how dynamic programming can be used as a tool ...
1
vote
0answers
27 views
Find exact sum in path
So the question is
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
0
votes
2answers
81 views
Two-Sum - Pre-sort Optimization Algorithm Design
🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?
🚀 Original Two-Sum
Determine whether there are two items whose ...
1
vote
1answer
54 views
Minimum sum of squared Euclidean distance between two arrays
Question:
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the ...
0
votes
1answer
55 views
approaching dynamic programing for problem
I want to find a solution to a problem that asked before.
in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-...
1
vote
1answer
108 views
Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming
If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \...
1
vote
1answer
25 views
Generating all the increasing subsequences
Given an array of integers, how can we generate all the increasing subsequnces of length of 4 ?
Example: given this list
l = [1, 2, 4, 5, 3, 6]
The answer should ...
1
vote
2answers
77 views
Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?
Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but ...
1
vote
2answers
41 views
About the pseudo polynomial complexity of the KnapSack 0/1 problem
I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
0
votes
0answers
15 views
Probability that BST has exact height
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
...
0
votes
0answers
24 views
Number of complete traversals of the circle in generalised Josephus problem?
In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (...
1
vote
1answer
29 views
Unconstrained subset sum vs constrained subset sum?
In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: ...
0
votes
1answer
79 views
For dynamic programming problems, how do we know the subproblems will share subproblems?
So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:
...
2
votes
1answer
50 views
0-1 Knapsack problem with item discounts
I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
1
vote
1answer
59 views
Recurrence formula for optimal binary search tree
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For ...
0
votes
1answer
51 views
How is equation 1 simplified to equation 2 as shown below
In CLRS (Intro to algorithms) on page 362, it says eqn(1) :
can be simplified to this equation(2):
I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
1
vote
1answer
37 views
Does this LCS algo generate all the CS or only all the LCSs?
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
0
votes
0answers
33 views
Optimal partitioning of n-arrays
You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.
The goal is to partition those arrays into K ...
1
vote
1answer
109 views
Linear Grammar in less than cubic time
I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ ...
0
votes
0answers
53 views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
1
vote
0answers
39 views
Algorithm to Check for Upper Bound of Levenshtein Distance
I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating ...
0
votes
1answer
35 views
Interval Scheduling problem with more than 1 machine
There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n ...
1
vote
1answer
150 views
Count subset divisible by 3
I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is ...
1
vote
0answers
26 views
Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?
First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to ...
1
vote
1answer
31 views
Find maximal subset with interesting weight function
You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
2
votes
1answer
19 views
Policy dependent on initial state distribution in finite horizon MDPs
Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition ...
3
votes
0answers
79 views
Speeding up the Rummikub algorithm - explanation required
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
1
vote
1answer
77 views
Longest common sub-sequences with a condition
A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length....
1
vote
1answer
58 views
Count minimum number of steps to destroy all blocks
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the ...
0
votes
1answer
53 views
Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of ...
