Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
987 questions
0
votes
1
answer
113
views
Runtime analysis of Fibonacci series
To compute the $n$th Fibonacci number, a recursive algorithm is as follows:
...
- 163
0
votes
0
answers
161
views
3-Partitions with same sum problem algorithm
this is the problem statement (3-Partition Problem): Partition a set of integers into three subsets with equal sums.
Input: a sequence of integers $v_1, v_2, ..., v_n$
Output: check if it is possible ...
- 1
1
vote
0
answers
32
views
Graph labeling through optimization of a quadratic form
Given a simple unlabeled graph $G = (V,E)$ with vertices $V=\{1,\ldots,n\}$, let $L(G)$ a labeled graph obtained by labeling (with distinct labels) the vertices of $G$ through any $l: V \rightarrow V$ ...
- 155
2
votes
1
answer
235
views
Find path in Directed Acyclic Graph from starting to ending node where each node is connected from an ancestor in the path
I am given a directed acyclic graph and I want to find all paths from a starting node to an ending node such that all child nodes are connected to previous ancestors. I'm not even totally sure how to ...
- 23
2
votes
0
answers
53
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...
- 21
0
votes
1
answer
106
views
Expressing a mathematical recurrence relation for the coin change problem with one parameter
I've recently begun studying about the dynamic programming paradigm, and came up across two variations of the coin change problem as described below:
Given a set of coin values $C = \{c_1,c_2, ...\}$, ...
- 103
0
votes
0
answers
95
views
Maximizing Edge Sum
So there is this question :
we are given a tree with n nodes. For each node, $i$ we are assigned two values : a $r_i$, that is the right boundary, and a $l_i$, which is the left boundary. We should ...
- 35
1
vote
1
answer
131
views
Showing Dijkstra's algorithm works for bridge negative edges
Let $G=(V,E)$ a directed graph with weight function $w:E \to R$. let $s \in V$ a vertex s.t it has path to any other vertex in $G$. Suppose that every negative vertex in this graph is bridge edge, ...
- 181
0
votes
1
answer
112
views
In the "House Robber" problem, why are there only two available actions and restricted movement?
Consider the House Robber problem:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing ...
- 103
1
vote
1
answer
62
views
Drive between two cities, dynamic programming
A car goes from city A to city B. Both route A and B have n sections. A[1...n] and B[1...n] keeps the traffic information about sections of route A and route B respectively in terms of minutes. The ...
- 11
0
votes
1
answer
152
views
Efficient Algorithm to Count Permutations of Boss Fights with Divisibility Constraints in an RPG Game
I'm trying to find an efficient algorithm to calculate the amount of permutations for this problem. I've only slightly simplified the problem to be easier to read. But the original problem, is Problem ...
- 340
2
votes
1
answer
177
views
Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $ n \times n $ Table
We have an $ n \times n $ table, and in each cell of the table, there is a number from $1$ to $ 2n $. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
- 367
0
votes
1
answer
70
views
Selecting an Induced Subgraph from a DAG with Specific Conditions
I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$.
My objective is to select an induced ...
- 367
0
votes
0
answers
76
views
Algorithm to "reverse" search/match pairs from results
Sorry, I don't know how to title it clearly.
There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
- 1
1
vote
1
answer
73
views
Algorithms for stacking gage blocks
I'm looking for algorithms for stacking gage blocks.
For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this...
Mitutoyo's 56 ...
- 131
3
votes
1
answer
129
views
Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs
Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
1
vote
1
answer
57
views
Given a $n \times n$ matrix $M$ find a subset of d rows and d columns so that the sum of the elements in their intersection in maximized
Given a $n \times n$ matrix $M$ of positive integers and a constant $d$. If $R,C \subset \{1,...,n\} $ let $$S_M(R,C) = \sum_{r \in R,c \in C }M_{i,j} $$
I want to find the sets $$R,C \subset \{1,...,...
- 225
0
votes
1
answer
397
views
Number of ways in which a '?' in a given string can be replaced with numbers from [0-9]
I came across this interesting problem in a test and I couldn't complete it.
There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the ...
- 101
2
votes
2
answers
164
views
No Neighbor Vertex Cover
Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
3
votes
2
answers
1k
views
Find 1s in almost all 0 array using comparisons only
So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python):
...
- 61
1
vote
1
answer
147
views
Knapsack Problem: Find Top-K Lower Profit Solutions
In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table":
...
- 111
1
vote
0
answers
102
views
Total combinations in DAG with upper bound on node value
There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
1
vote
1
answer
66
views
Efficient way of computing average ALL function over matrix rows
Assume that a matrix $M\in [0;1]^{n\times d}$ is given, i.e., all values in the matrix are in the range 0 to 1. I would like to compute the following function for all rows of $M$:
$$
f(m_1,m_2,...,m_d)...
- 226
1
vote
0
answers
98
views
How do I optimally fuse nodes in a tree structure?
I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
- 239
2
votes
1
answer
67
views
Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval
PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-...
- 121