Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
972
questions
0
votes
0
answers
37
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 ...
- 330
1
vote
0
answers
34
views
Longest non-decreasing contiguous subsequence with at most one substitution
Is there any algorithm that can count the length of the longest non-decreasing contiguous subsequence with at most one substitution?
For example, given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the ...
2
votes
1
answer
88
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 ...
- 157
2
votes
1
answer
131
views
Minimum number of intervals from a set to cover all intervals of another set
There are two sets of intervals provided to us.
target = {{11,13}, {7,10}, {0,3}, {6,6}}
space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}}
I need to find the minimum number of intervals I can pick from ...
- 23
0
votes
1
answer
32
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 ...
- 157
0
votes
1
answer
300
views
Counting Towers Recurrence Verification From CSES Problem Set
Problem Statement:
Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.
For example, here are some possible ...
- 1
0
votes
0
answers
38
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
2
votes
1
answer
140
views
Tree algorithm - arrange integer array numbers to form largest number
I have solved leetcode's Largest Number.
I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
- 123
1
vote
1
answer
28
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
193
views
Can every greedy problem be solved using dynamic programming?
Can every problem with a greedy solution be solved using dynamic programming? Why or why not?
I'm not completely sure how to formally reason about this, my understanding about the structure of ...
3
votes
1
answer
73
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 ...
0
votes
0
answers
31
views
Maximum density knapsack with initial volume and constraint on number of items
Given $\{\rho_i,v_i\}_{i=1}^N$, the densities and volumes of $N$ items, and $K\in \mathbb{Z}_+$. Let $v_0=1$ be the initial volume, and the initial mass is zero. The values $\rho_i,v_i\in \mathbb{R}_+$...
- 101
1
vote
1
answer
31
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
-1
votes
1
answer
42
views
Minimize Cost to Split Integer Arrays
There is a sorted integer array $a_1 \dots a_n$ and an integer $1 \leq k \leq n$, we need to figure out the minimized total cost to group this integer array into $k$ groups. The cost per group is mean(...
0
votes
1
answer
197
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
0
votes
0
answers
34
views
Algorithm for Minimum Subset Sum Greater Than K While Minimizing Subset Size
Given an array of positive integers and a positive integer K, I need to find the minimum subset sum S greater than K, and the size of the smallest subset that sums to S.
I have attempted to first find ...
- 1
2
votes
2
answers
108
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 ...
2
votes
1
answer
111
views
Dynamic Programming as DAGs - Solution Always Shortest Path?
I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the ...
- 29
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
0
votes
0
answers
65
views
Find maximum sum subgrid under constraint
Give a positive $m$ by $n$ matrix as input, choose a set of elements such that for any 2 by 2 submatrices, at most 2 elements are chosen. Return the maximum sum of chosen elements among all possible ...
1
vote
1
answer
69
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
0
votes
0
answers
42
views
Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)
For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
- 101
1
vote
0
answers
65
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
votes
1
answer
48
views
How to get the TSP using DP algorithm can use 40 vertices?
I`m currently doing my homework that solving TSP using DP algorithm or branch and bound algorithm or backtracking algorithm only to solve up to 40 vertices and I can solve up to 30 vertices when I try ...
- 1
1
vote
1
answer
31
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)...
- 216
1
vote
1
answer
295
views
Number of stops during trip - Dynamic programming algorithm
I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
- 23
1
vote
0
answers
42
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
3
votes
1
answer
206
views
is there an efficient algorithm to find the optimal partition of a matrix?
Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down ...
- 1,006
2
votes
1
answer
23
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
1
vote
2
answers
202
views
I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems
How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
- 119
1
vote
1
answer
159
views
Dynamic Programming problem about intervals
This is algorithms and data structures assignment and I have been thinking 3 days about it.
You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in ...
- 11
0
votes
0
answers
32
views
Intervals with costs and limited resources, dynamic programming
I have been trying to solve the following problem. I have n intervals each with a cost.I want to choose a subset of the intervals that maximizes the cost but with the following constraint. Each ...
- 13
0
votes
0
answers
34
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
0
votes
0
answers
115
views
Dynamic programming problem for minimum cost tower placement
I have an algorithmic problem in which I have a highway that is a straight line of length $n$ and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
1
vote
0
answers
40
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input.
I can only interchange one row ...
- 11
0
votes
0
answers
14
views
Better implementations for this dynamic program to solve optimization problem?
In the code below, I describe a problem and provide a backtracking implementation in Python that solves it:
...
- 195
0
votes
0
answers
19
views
Optimize clothing in RPG considering set bonuses
In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
- 1
0
votes
0
answers
35
views
Knapsack with weight swaps
I have a problem that is 0/1 knapsack, but you are also able to swap the weight of 2 items up to k times. I came up with a O(nkc) solution, but I am looking for a faster o(n*c) solution. I think the ...
0
votes
1
answer
84
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
- 1
0
votes
0
answers
26
views
Optimizing an Algorithm for Timestamp-Aware Partitioning of Data
My Problem
I'm currently dealing with an algorithmic problem that involves two input lists:
A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$.
A list of triples ...
2
votes
0
answers
124
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 21
0
votes
0
answers
38
views
Find submatrix with sum as close to k as possible
What is the efficient algorithm to find a submatrix (must be rectangle) with a sum that is as close as possible to k? Matrix consists only of nonnegative integers. Iterating through all possible ...
- 1
0
votes
0
answers
26
views
Dynamic Programming for LCS problem
I understand that in Dynamic Programming approach the subproblems are solved in a particular order from smallest to largest. In LCS how the subproblems sizes are defined and in which order it is ...
1
vote
1
answer
413
views
CSES problem Two Sets II
Your task is to count the number of ways numbers $1,2,…,n$ can be divided into two sets of equal sum. For example, if n=$7$, there are four solutions:
${1,3,4,6}$ and ${2,5,7}$,
${1,2,5,6}$ and ${3,4,...
- 131
0
votes
0
answers
19
views
Feedback Vertex Set in graphs with bounded tree width using Dynamic Programming
What is the subproblem associated with this DP and what are the terms to calculate?
0
votes
1
answer
91
views
Matching points on a plane with maximum total weight
I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
- 105
1
vote
1
answer
68
views
In a directed graph, efficiently determine node reached after traveling k edges from the starting node
I am trying to solve a problem where I am given a directed graph with $n$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $1$ to $n$. Starting at ...
- 13
1
vote
0
answers
71
views
Maximize sum of matrix after deleting K rows and K columns
You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
- 111
0
votes
1
answer
78
views
Efficient algorithm for finding the target sum
Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
- 1
1
vote
1
answer
77
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size ...
- 411