Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
60 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 ...
Viktor's user avatar
  • 23
0 votes
1 answer
21 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 ...
Ferran Gonzalez's user avatar
0 votes
1 answer
60 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 ...
Ved K's user avatar
  • 1
0 votes
0 answers
35 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. ...
herhor67's user avatar
2 votes
1 answer
118 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 ...
ccot's user avatar
  • 123
0 votes
1 answer
20 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 ...
David Carpenter's user avatar
-3 votes
1 answer
73 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 ...
proof-of-correctness's user avatar
3 votes
1 answer
71 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 ...
Daniel García's user avatar
0 votes
0 answers
25 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}_+$...
user1000039's user avatar
1 vote
1 answer
28 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,...,...
Sander's user avatar
  • 203
-1 votes
1 answer
40 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(...
user168862's user avatar
0 votes
1 answer
83 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 ...
ABGR's user avatar
  • 101
0 votes
0 answers
28 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 ...
mertvy's user avatar
  • 1
2 votes
2 answers
102 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 ...
Daniel García's user avatar
1 vote
1 answer
37 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 ...
Macroxela's user avatar
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): ...
user555076's user avatar
0 votes
0 answers
29 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 ...
vyjtkbyykyhuk's user avatar
1 vote
1 answer
53 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": ...
slaw's user avatar
  • 111
0 votes
0 answers
41 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 ...
mishar's user avatar
  • 101
1 vote
0 answers
62 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 ...
Aryan Agarwal's user avatar
-1 votes
1 answer
38 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 ...
Tuan's user avatar
  • 1
1 vote
1 answer
30 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)...
mto_19's user avatar
  • 206
1 vote
1 answer
188 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 ...
FarsoFracico's user avatar
1 vote
0 answers
39 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, ...
RunOrVeith's user avatar
3 votes
1 answer
202 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 ...
Simd's user avatar
  • 996
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-...
Shred's user avatar
  • 121
1 vote
2 answers
116 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 ...
Hardik Dhuri's user avatar
1 vote
1 answer
118 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 ...
guitarMan's user avatar
0 votes
0 answers
28 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 ...
SotirisD's user avatar
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 ...
Sooraj S's user avatar
  • 139
0 votes
0 answers
100 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 ...
Izzy Handkammer's user avatar
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 ...
HelpmePlease's user avatar
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: ...
lafinur's user avatar
  • 195
0 votes
0 answers
18 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 ...
Ferazhu's user avatar
0 votes
0 answers
31 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 ...
Nathan Dai's user avatar
0 votes
1 answer
63 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 ...
Sachin's user avatar
  • 1
0 votes
0 answers
25 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 ...
mathbreaker's user avatar
2 votes
0 answers
122 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 ...
quTANum's user avatar
  • 21
0 votes
0 answers
37 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 ...
qpexxtt's user avatar
0 votes
0 answers
25 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 ...
user163414's user avatar
0 votes
1 answer
228 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,...
Charlie's user avatar
  • 11
0 votes
0 answers
17 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?
Anonymous's user avatar
0 votes
1 answer
82 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 ...
Grigori's user avatar
  • 105
1 vote
1 answer
60 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 ...
Falls2879's user avatar
1 vote
0 answers
60 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 <...
jeffkmeng's user avatar
  • 111
0 votes
1 answer
75 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 ...
jamesw1's user avatar
0 votes
0 answers
15 views

I have the following OCaml code, what would be the output for static scoping and dynamic scoping?

...
Penny Bas's user avatar
1 vote
1 answer
72 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 ...
Mathguy's user avatar
  • 411
0 votes
0 answers
209 views

Best time to buy and sell stocks with multiple buy transactions are allowed and can sell all shares at once

I've been trying to solve a variation of this problem https://stackoverflow.com/questions/62389658/best-time-to-buy-and-sell-stocks-when-allowing-consecutive-buys-or-sells You are given an input array ...
TWhite's user avatar
  • 37
3 votes
1 answer
151 views

Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?

On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
Rabbiiiiit's user avatar

1
2 3 4 5
20