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
0answers
17 views

My algorithm to find Longest Palindromic Substring does not work correctly in some cases

Question: Given a string s, return the longest palindromic substring in s. Example 1: Input: ...
0
votes
0answers
39 views

Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive. For instance, solving the rod-cutting problem by this algorithm: ...
0
votes
1answer
56 views

Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank

Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) : In this challenge, you will be given an array $ B $ and must determine an array $ A $ ....
-1
votes
1answer
34 views

Proving existence of an optimal substructure for the DP problem "Equal" from HackerRank

Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank? Problem statement: My attempt: Let $ A = [ a_1,a_2,...,a_n ] $ be our ...
1
vote
1answer
43 views

Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?

In dynamic programming: 1. what is the definition of the space of subproblems? does it have a mathematical definition? 2. why is it necessary to have an arbitrary index for the subproblem to vary? To ...
1
vote
1answer
38 views

What are the reasons for solution assumptions behind the longest subsequence problem?

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...": ...
0
votes
0answers
42 views

Given a set of integers and target, find all subsets of size k such that sum of elements of each subset equals target

I am trying to solve below problem Given a set of integers A, and target integer, find all subsets of size k such that sum of elements of subset equals target. One approach could be enumerating all ...
0
votes
1answer
56 views

speed up straightforward solution using dynamic programming

i recently got onto the following problem: we consider the following array: A = [2, 3, 6, 1, 6, 4, 12, 24] we need to count the number of times these two ...
1
vote
1answer
35 views

How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?

I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
0
votes
0answers
21 views

Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
1
vote
0answers
31 views

Is weighted interval scheduling where the weights are the interval lengths simpler/faster

In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time. If the weights of the intervals are their integer lengths,...
0
votes
0answers
44 views

Bin packing problem using bit masking

We have n box and an array of weights, where weight of ith box is given by arr[i]. We have a container which can carry a maximum weight of w. Now we have to find minimum number of containers required ...
1
vote
0answers
176 views

Minimum no of swaps to be done in an array such that, no two adjacent elements are same

Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex- n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or a[5] ) n = 8,...
2
votes
0answers
31 views

Constrained/Optimal Topological Order to enhance/reduce the performance/memory usage of other algorithms

I originally posted this question here Lets assume we have a highly connected directed acyclic graph (DAG, more edges then nodes). Since it is a DAG, we can retrieve a topological order of nodes to ...
0
votes
0answers
173 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
45 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
18 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
48 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
52 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, ...
0
votes
1answer
36 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
27 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
46 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
50 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
30 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
44 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
40 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
41 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
83 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
65 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
89 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
274 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
22 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
36 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
114 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
29 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
42 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
47 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
64 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
91 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
106 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
168 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
79 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
47 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
66 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 ...
2
votes
1answer
73 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
47 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
2 3 4 5
16