Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
-1
votes
0answers
23 views

Minimum cost required to cover a line with line segments

We are given a line segment $[1, n]$ with $m$ smaller line segments $[l_{i}, r_{i}]$. An example being $[1, 4]$ and line segments ${[1,2], [2,3], [3,4]}$. We can cover this using first and third ...
0
votes
0answers
17 views

CSES Question - Tower [closed]

Ques Link: https://cses.fi/problemset/task/1073/ Code Link: https://pastebin.com/S9nzVJVa In CSES question : Towers, I know it can be solved using sets with greedy approach but I was trying to do ...
0
votes
0answers
27 views

Minimum Number of Refueling Stops with Dynamic Programming

This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
0
votes
0answers
36 views

Minimize the average distance from each cities to the closest hospitals

There are n cities [1, 2, 3, .... n] and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to ...
0
votes
0answers
17 views

How do I group elements of a list into windows of predefined sizes with minimum cost given longer windows are cost efficient?

You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. ...
2
votes
1answer
37 views

Number of subsequence with k distinct characters

"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order." Suppose we have string s="aabca&...
1
vote
3answers
33 views

Greedy Algorithm: Optimal Substructure

I don't have a CS degree but I have recently taken up studying algorithms very seriously. I have been studying greedy and dynamic programming for days and I come across the below definition a lot, ...
-2
votes
0answers
46 views

An Dynamic Programming algorithm for this problem(Largest Tower)

We have some blocks of the tower(n) with the same Height(each of them has 1 as its Height) each block has Weight(w) and maximum Tolerable weight(L).each block can withstand a certain weight(L). if a ...
0
votes
1answer
31 views

reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $$ x_{k+1} = f(x_k,u_k), k=0,\dots,N-1 $$ given some $x_0$ and ...
0
votes
0answers
22 views

Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
1answer
41 views

DAG for contiguous subsequence of maximum sum

I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous ...
2
votes
0answers
38 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
3
votes
0answers
49 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
0
votes
1answer
24 views

Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
0
votes
0answers
39 views

Count of different ways to express N as the sum of given numbers

I'm working on a case and I need some help :) I need to find number of ways and solutions itself to express N as the sum of given numbers. So, Sum (N) = 600 and the numbers from which I need to get ...
3
votes
1answer
37 views

What's the runtime complexity of this algorithm for breaking up string into words?

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
0
votes
0answers
19 views

Alter Sankoff's Algorithm to give all optimal solutions

I'm trying to find a way to alter the Sankoff's Algorithm so it will trace back all the optimal solutions and not only one. Is it possible?
1
vote
1answer
40 views

Compute sum of edges in paths from source to target node?

Given a directed acyclic graph G = (V,E). Suppose that the vertices are in topological sort, in particular there exist an edge $(u,v) \in E$ if u <v (see the graph below). The weight $w(u,v)$ on ...
2
votes
1answer
78 views

Minimizing flow on a 2D matrix network

I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it ...
0
votes
1answer
64 views

Group testing puzzle

I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers. I can't tell which ...
0
votes
0answers
84 views

Dividing a array to into k parts using dynamic programming

I am thinking about how to break an array into k parts using DP with the following requirement. Array A of size n divided into k parts All elements are positive integers and order is fixed. The ...
1
vote
1answer
266 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
20 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
34 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
105 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
28 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
38 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
35 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
62 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
56 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
104 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
123 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
72 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
33 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
60 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
30 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
68 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
67 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
87 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
19 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
39 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
2answers
167 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
75 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
72 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
47 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. ...

1
2 3 4 5
16