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
1answer
23 views

FPT for Special Matching

In Special Matching, we are given an undirected graph $G$, a function $w:E\rightarrow\mathbb{N}$, and an integer $k$. The objective is to decide whether $G$ contains a matching $M$ of size at least $k$...
0
votes
0answers
23 views

Intuition behind : recursive algorithm takes exponential time [duplicate]

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
1
vote
0answers
59 views

Maximum money that can be made

Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...
1
vote
0answers
24 views

What are some examples of overlapping subproblems that don't have an optimal substructure thereby we cannot solve it using dynamic programming?

I believe problems like quicksort and other divide-and-conquer are problems that have optimal substructure but do no have any overlapping subproblems. I hope I'm correct here. But I'm unable to think ...
1
vote
0answers
32 views

Proof for knapsack with unlimited items

This is the knapsack problem where the items are unlimited. Let $K(w)$ be be the maximum value achievable for the knapsack capacity of $w$, and $w_i$ and $v_i$ are the weight and value of the item $i$....
4
votes
1answer
33 views

Is there a more efficient way to obtain the optimal input sequence in this finite-state system

Context: Consider $M$ finite state systems with evolution given by: $$ x^i_{k+1} = f(x_k^i,u_k) $$ where $x_k^i\in\{1,\dots,X\}$ is the state of system $i\in\{1,\dots,M\}$, $k\geq 0$, and $u_k\in\{1,\...
3
votes
0answers
46 views

Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
1
vote
2answers
26 views

Getting three numbers from set that combined gives n

I have run into a little problem that I have been pondering about, and can't figure out a good solution for. Let's say that I have a set of numbers like this one: ...
0
votes
0answers
99 views

Multivariate piecewise linear interpolation

I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm. ...
0
votes
1answer
23 views

Dynamic program to solve operation over digits

i have faced this problem that i can not solve. assume i have a number like n. I want to do m operation over each digit. in each operation every digit is added by one for example if my number is 1239 ...
2
votes
1answer
56 views

Cover 2 by n binary matrix with submatrices of minimum total size

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
1
vote
0answers
79 views

Clustering points on a line

Given pixel values $r_1,r_2,\dots,r_n \in \{0,\ldots,255\}$ and $k$, find $$ \min_{v_1,\ldots,v_k} \sum_{i=1}^n \min_{1 \leq j \leq k} (r_i - v_j)^2. $$ My attempt: Let $F[L,c]$ be the minimum cost, ...
1
vote
1answer
65 views

How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
1
vote
1answer
31 views

Finding the uniqueness of longest increasing subsequence

I have a problem related to a common dynamic programming problem LIS. I got LIS function that takes arr as an input and returns the ...
1
vote
0answers
18 views

Thought Process for largest Container of Water Problem

There is a common leetcode problem that asks Given $n$ non-negative integers $a_1, a_2, \dots, a_n$, where each represents a point at coordinate $(i, a_i)$. Then $n$ vertical lines are drawn such ...
0
votes
1answer
127 views

Number of ways to delete edges from an undirected tree such that each subtree has exactly 1 fruit

An undirected tree has $n$ nodes and some nodes contain a fruit. How many ways can we remove edges from the tree such that each sub-tree has exactly one node with fruit in it? I found this question in ...
-1
votes
1answer
100 views

Dynamic programming to find number of ways to divide string into primes

I am studying for final algorithms exam and saw this question: Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers >= 2....
-1
votes
1answer
40 views

Write n in terms of multiplication of numbers from A=[1,...,n] such that the total cost of chosen number is maximum

We want to write n in terms of multiplication of numbers from A = [1,...,n] such that the total cost is maximum. The cost of choosing the ith number is cost[i]. ...
1
vote
0answers
18 views

Discounted Optimal Stopping

The model is as followed: Consider an infinite horizon discounted problem $(0 < γ < 1)$ in which the state space is finite, with $n$ states, and there are only two possible decisions: stop or ...
0
votes
2answers
115 views

LQR optimal control of accumulator via dynamic programming

Let $$ x_{k+1} = x_k + u_k, \qquad x_0 = 5 $$ where $k \in \{ 0,1,2,3 \}$, define the return function $$ - \sum_{k=0}^3 \left( x_k^2 + u_k^2 \right) $$ with the following inequality constraints on the ...
1
vote
1answer
59 views

Find if it's possible to partition a set into 3 disjoint sets each with same sum

Question: I came a cross a problem where we have a set of numbers $W= \{x_1, \cdots, x_n\}$ where repetition of numbers is allowed. We would like to find out whether we can find out 3 disoint sets ...
0
votes
0answers
23 views

Minimizing total penalty from trips over all travel days

I would like to discuss with you please the following problem and it's solution. Setup: We are travelling with the following constraints: You can only drive in the daytime. On any given day, you can ...
1
vote
1answer
21 views

Variation on Matrix Chain problem -- compute diagonal only?

How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square) First computing the matrix product and then ...
2
votes
0answers
45 views

Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
1
vote
1answer
53 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
24 views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
0
votes
0answers
22 views

Finding all k-partitions with additional constraints

The partition problem is a very well known one. To partition an integer array into k equal sum partitions. My problem is I want to partition them in such a way that the sum of their partitions equals ...
1
vote
0answers
29 views

Longest substring creating palindromic substring in other string

Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$. I ...
1
vote
1answer
54 views

House Robber DP Algorithm (Not three in a row)

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
0
votes
1answer
69 views

Is top-down dynamic programming always recursive?

I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm: ...
0
votes
1answer
59 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
48 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
47 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
39 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
49 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
60 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
52 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
35 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 ...
0
votes
0answers
34 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
57 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
267 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
42 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
283 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
63 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
70 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
62 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, ...
1
vote
1answer
63 views

Solving problems by dynamic programming plus 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) $$ where $k \in \{ 0,\dots,N-1 \} $, ...
0
votes
0answers
33 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
57 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 ...

1
2 3 4 5
17