Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
31 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
-1 votes
0 answers
22 views

Backpack assigment

Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
mmartiss's user avatar
0 votes
0 answers
11 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
37 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
12 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
  • 181
0 votes
0 answers
16 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
19 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
30 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
24 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
1 vote
0 answers
88 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
  • 11
0 votes
0 answers
32 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
24 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
58 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
14 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
76 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
  • 95
1 vote
1 answer
44 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
31 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
50 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
46 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
80 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
94 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 vote
1 answer
148 views

knapsack with graph connectivity constraints

I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally: The input is an undirected ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
74 views

How can this problem be solved in $O(n^{3/2}log(n))$ time?

I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible? Let $D[1 .. n]$ be an array of digits, each ...
Johan's user avatar
  • 13
2 votes
1 answer
61 views

Minimal set of elements needed to satisfy property counts

I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
Aderyn Thomas's user avatar
-2 votes
1 answer
57 views

Programs with feedback?

Suppose we have a program like this: ...
Volpina's user avatar
  • 97
1 vote
1 answer
89 views

Longest Increasing Co-Prime Subsequence?

This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways. Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing ...
bihariforces's user avatar
1 vote
1 answer
51 views

Minimum coins to make change when real numbers are allowed

There is the classical version of the minimum coins to make change problem where the change and the set of coins available are all integers. Given an infinite amount of each type of coin, we're asked ...
Rohit Pandey's user avatar
4 votes
1 answer
109 views

Telescope Scheduling Predecessors

In Algorithm Design and Applications by Michael T. Goodrich and Roberto Tamassia Chapter 12.3 there is a presentation of a problem called the Telescope Scheduling problem. Given n requests each with ...
giannisl9's user avatar
1 vote
0 answers
22 views

Formulating a bottom-up dynamic programming premise for a board game

The game being played here has the following rules, played be a singular player: there is a 5x5 board, where some tiles are highlighted and some are not. From here, the player can highlight the blank ...
Some Guy's user avatar
1 vote
0 answers
44 views

Dynamic Programming: Counting *cycles* consisting of distinct numbers

I was thinking about this question and thought about it for quite a while but couldn't come up with an answer. Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
Gareth Ma's user avatar
  • 111
0 votes
0 answers
26 views

Optimality in greedy task

There is a well-known problem of the best time to buy and sell stock. Assume now we have two arrays, SELL and BUY. Each time SELL[i] > BUY[i]. Assume we have initial budget B, and we can buy any ...
openspace's user avatar
  • 151
2 votes
2 answers
99 views

Zero sum game: dp recursion strategy

Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
rickyviking's user avatar
0 votes
1 answer
72 views

How to cover elements with minimum amount of elements

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the ...
Ally Zane's user avatar
0 votes
0 answers
65 views

House Robber Problem Variation with Risk/Cost to Rob Each House

I came across a modification of the classic house robber problem where there is a cost to robbing each house, and we want to maximize the amount robbed using the array (exactly as in the original ...
user197328534535's user avatar
1 vote
1 answer
27 views

Constrained precedence parsing

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem? The setup is as follows: we are given $n$ ...
Mario Carneiro's user avatar
0 votes
0 answers
29 views

Algorithms for finding number of sequences with length N and displacements less than k

The sequences are made up of only digits. A displacement is defined as pair $(i, j)$ such that $i > j$ and $A[i] < A[j]$. For example, 423 has 2 displacements. The question is to find the number ...
Mahdi Khodabandeh's user avatar
0 votes
1 answer
58 views

Why does the non-adjacent sum problem have optimal substructure?

In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $[1,4,3,8,5]$ the largest sum of non-adjacent ...
jem do's user avatar
  • 1
-2 votes
1 answer
104 views

Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
abcd's user avatar
  • 1
0 votes
0 answers
31 views

Upper bound of traveling salesman problem via dynamic programming

For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be \begin{equation} \sum_{k=1}^{n-1} O\left(\left(\begin{...
Jung's user avatar
  • 101
0 votes
0 answers
46 views

Is there a sorting program or formula to sort and place individuals in classes based on preferences

I am looking for a formula or program to help place people in classes based on their preferences. The elements of the problem are: There are 30 class choices a student can pick from. There are 400 ...
Nick B. 's user avatar
1 vote
1 answer
393 views

Placing K gas stations among n cities to minimize distance

There are $n$ cities on a highway with coordinates $x_1$ , . . . , $x_n$ and we aim to build $K < n$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and ...
Muffinlicious's user avatar
2 votes
1 answer
62 views

Checking forbidden moves in Renju

I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works. Renju is a board game played on a 15x15 Go board. There are two players in the ...
Kyaw Shin Thant's user avatar
2 votes
0 answers
75 views

Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
Sabe's user avatar
  • 21
2 votes
2 answers
596 views

Select a subset of k intervals which form maximum length if we take union of these k intervals

Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals. Note that there are 2 cases ...
Kitwradr's user avatar
  • 123
1 vote
2 answers
134 views

How do I find the most even combination for two arrays

I have two arrays that both contain $n$ elements (positive, non zero, not negative) $\{x_1\dots x_n\}$ $\{y_1\dots y_n\}$ I want to pair them up optimally, one from each array, so that the pairs come ...
Ally Zane's user avatar
0 votes
1 answer
66 views

Compute the maximum length of an increasing digital subsequence given an array of digits

Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson. Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
MR_'s user avatar
  • 1,564
1 vote
0 answers
139 views

Tabular Meta-Learning in RL

There are various meta-learning algorithms in RL that are proposed for settings when we have a (deep) neural network and the policy (or the value function) are parameterized as such. Can these methods ...
Perissiane's user avatar
0 votes
1 answer
54 views

Confused on Bellman Ford

We have a graph where we want to get from node u to v in the shortest path possible. I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
smarty_pants's user avatar
1 vote
1 answer
92 views

Another Game Theory Problem

We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
Identicon's user avatar

1
2 3 4 5
19