Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
758
questions
1
vote
1answer
213 views
If P = NP, would dynamic programming be obsolete?
I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic ...
1
vote
0answers
14 views
Resources on Dynamic Programming with Indefinite Recursion
I am trying to explain the value iteration method that is used in reinforcement learning. The method is used to estimate a solution to a recursive equation like:
$ Return(state_t,action_t) = Reward(...
2
votes
1answer
22 views
dynamic programming: longest palindromic subsequence, recurrence relation question
Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
I want to restate the question at the ...
0
votes
1answer
95 views
How to derive max amount of items from DP table of Knapsack problem?
I have a little bit changed algorithm for 1-0 Knapsack problem.
It calculates max count (which we can put to the knapsack) as well.
I'm using it to find max subset sum which <= target sum. For ...
1
vote
0answers
25 views
Sub-matrix with minimum size of $k$ and minimum sum
We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
1
vote
1answer
31 views
Dynamic programming: Maximize total value
I was trying to solve this problem using dynamic programming.
We have $n$ objects in a row where each object has a value represented with a positive number.
This is encoded with an array $V[1], . . . ,...
1
vote
1answer
30 views
Time Complexity of Memoized Solution
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
4
votes
0answers
60 views
Number of permutations with satisfactory triangles
We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
29 views
Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own
I had an online round at a company where I was asked this question.
There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.
Each item has three ...
2
votes
1answer
98 views
What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?
I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it ...
1
vote
2answers
102 views
Longest sequence of dominoes
Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
1
vote
0answers
46 views
0/1 Knapsack problem with minimal cost
so i have this problem where:
I have to accomplish a challenge A with n quests. Each quest gives me:
p points and
needs t time to be done.
The object is to complete the challenge A that needs M ...
1
vote
1answer
26 views
Can the House Robber problem be solved with a Sliding Window solution?
I was reading an article on how to solve sliding window problems and it said:
Fast/Lagging
This one is a little different, but essentially the slow pointer is simply referencing one or two indices ...
1
vote
1answer
57 views
Greedy algorithm for maintaining drugs
Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.
My answer is as follows:
I use ...
0
votes
0answers
49 views
Dividing a group into two groups with equal sum
Let $P = \{p_1, \dots , p_n\}$, where $p_i ∈ \{1, \dots , K\}$ is the price of the object $i$. Check if the objects can be divided equally.
In other words, there are $n$ objects with each price being ...
0
votes
0answers
23 views
Dynamic Programming, lru-cache, “minimum weight of a number”
I'm struggling with the following problem: The weight of a correct arithmetic expression, consisting only of the strings 1, x, +, is defined as the number of 1s appearing in the expression. Each ...
2
votes
1answer
64 views
Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
0
votes
0answers
19 views
Can the two optimal subproblems of the recurence formula below be reduced to one subproblem given the assumtions stated in the description below
In CLRS (Intro to algorithms 3rd Edition) on page 362, it says eqn(1) :
Lets Assume that you are given the cost of matrix multiplication for $A_{i}..A_{j}$ is $C[i,j]$ .
$C[i,j]$ is the Number of ...
0
votes
0answers
43 views
Counting number of sequences summing to target
This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading:
We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
1answer
66 views
Maximize 5-independent gifts on a path
Question: Assume there are $n$ distinct gifts on the real line. Their
positions are $\{x_1, ..., x_n\}$ and each of them has an individual
value $p_i$.
Now you can choose a subset of them such that ...
1
vote
1answer
84 views
Dynamic programming for graph splitting
I have a directed graph which has edges between every vertices $i$ and $j$ such
that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two ...
0
votes
2answers
14 views
Longest common subsequence solution reconstruction during DP is wrong
I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why ...
6
votes
0answers
81 views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
0
votes
1answer
20 views
Finding shortest path for DAG using dynamic programming vs topological sort?
Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
1
vote
1answer
24 views
Sum of products over k-permutations
Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to ...
3
votes
1answer
140 views
Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$
I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
1
vote
1answer
26 views
What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions
Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the ...
3
votes
1answer
74 views
Completing tasks on a graph
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
0
votes
2answers
65 views
Question concerning subset sum problem: split into 3 equal subsets
Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$. Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i....
1
vote
0answers
46 views
Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]
I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
0
votes
1answer
134 views
Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions
I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ ...
1
vote
1answer
42 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 $\...
1
vote
1answer
76 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
25 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
24 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
57 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
85 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
55 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
34 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
123 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
127 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
62 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+...
0
votes
1answer
38 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
106 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
59 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
36 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
2answers
138 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 ...
0
votes
2answers
43 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
28 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 ...
