Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
869
questions
0
votes
0
answers
7
views
Dynamic Time Warping and Similarity Measures
I have a multidimensional time series on which I would like to perform some clustering. I have been looking at DTW as a distance metric since my series are not always aligned in time. The problem I ...
- 1
0
votes
0
answers
31
views
Find The Least Waste When Sawing Wood Planks In A Specific Order
Similar to one of the questions that was posted here roughly 4 years ago. Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 50cm 30cm and 20cm. What kind of bottom-up ...
- 1
1
vote
0
answers
22
views
Minimize sum of products of partition [closed]
I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e.,
$$
\min_{X,Y : X \cup Y = A} \...
- 11
0
votes
0
answers
11
views
Pursuit-evasion graph problem Top down DP approach?
I'm solving this problem here to learn about pursuit-evasion problems https://leetcode.com/problems/cat-and-mouse/
Basically cat starts at 2, and mouse starts at 1 (goes first) to escape to 0 and they ...
- 111
0
votes
1
answer
25
views
Dynamic programming , Matches game and winning strategies
The question is:
There are 219 matches on a table and 2 players , each player can take 1,3 or 4 matches off the table , winner is who takes the last match.
is there a winning strategy that guarantees ...
1
vote
0
answers
24
views
Algorithm to determine maximum difference between different sets of a graph
I saw this image only, and it got me thinking: is this the maximum area difference between a contiguous region and Los Angeles County, such that the population of that region is smaller?
Formally, ...
- 111
1
vote
0
answers
13
views
Are these representations of the Bellman Equation equivalent?
I've found two slightly different Bellman Equations. Are they totally equivalent?
I see the one on the bottom has an s' in the reward. Does this or anything else about the groupings change anything ...
- 119
1
vote
1
answer
69
views
Generating the n-th number with k bits set, is it possible?
Generating numbers with $k$ bits set for a poker simulation
Context
I'm trying to generate all possible Texas Hold'em games for $p$ players, which means there will be at most $2 \cdot p + 5$ cards at ...
- 135
0
votes
1
answer
29
views
Why dont I need to memoize maxHeight in the problem below
I see this occasionally when solving Dynamic programming questions. I like to solve dp questions using recursion, then Memoize it based on the number of parameters I pass to the recursive function.
...
- 45
0
votes
0
answers
50
views
What is being summed in the Bellman Equation and why?
What is being summed and why?
$s'$ is the next state. Don't we just want the next state with the max value?
There is an $s'$ under the summation, so are all the possible $s'$ in $P$ and the $s'$ in $V(...
- 119
0
votes
2
answers
77
views
Finding minimal amount of coins to reach n
According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.
The problem is such:
You ...
- 51
0
votes
0
answers
12
views
What is the difference between Optimal Control and Dynamic Programming?
I am reading Reinforcement Learning by Sutton and Barto, in which they mention dynamic programing and optimal control very often and as two different approaches. I wonder, what are the commonalities ...
- 13
0
votes
0
answers
38
views
Is there linear solution for the hotel problem
You are going on a trip from point $s$ to point $f$, in the way there
are $n$ hotels, $p_1, p_2,..., p_n$ each denotes the number of $km$
from $s$. You must complete the trip by at most $t$ days ($t&...
- 241
0
votes
0
answers
36
views
Is there a name for a directed graph where we cannot re-enter a vertex that we leave (to a different vertex)?
I am wondering if there is an "official" name for a directed graph where we cannot re-enter a vertex once we leave it to a different vertex. Here's an example of one such graph, where once ...
- 1
-1
votes
1
answer
28
views
Modified knapsack problem with multiple boxes to choose from
I have seen the solution to the knapsack problem and understand it. But I am trying to
come up with a dynamic programming solution to the following problem, which is a modified
a version of the ...
1
vote
0
answers
40
views
Is there a pseudopolynomial time algorithm for this subset sum variant?
The subset sum problem is: given a list of $n$ positive integers, and a positive number $T$, find a sub-list with largest sum that is at most $T$. The problem can be found in time polynomial in $n$ ...
- 5,704
1
vote
1
answer
19
views
Efficient search of a large set of documents to find documents that only contain a particular set of words
Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language.
Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
- 111
3
votes
1
answer
74
views
Allocating m rooms of varying capacity to n booking requests of varying sizes
I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize ...
- 131
1
vote
2
answers
56
views
Counting the number of parenthesization
I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says:
Denote the number of ...
- 23
1
vote
1
answer
113
views
Formal Proof on why Greedy isn't working on one Particular Problem
Problem
You are given two integer arrays nums and multipliers of size n and ...
- 231
1
vote
0
answers
28
views
Unusual version of a binary search algorithm
For one dimensional, continuous binary search most effective algorithm would remember boundaries.
For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
1
vote
1
answer
87
views
Time complexity analysis for dynamic programming using memoization
I am trying to figure out the time complexity for "Regular Expression Matching" problem.
Problem statement is simple, only meta characters allowed are '.' and '*'. Actual problem statement ...
1
vote
2
answers
51
views
Optimizing an arbitrary function of 10 variables
Let us be given a function $f(x_1,\dots,x_{10})$ of multiple variables $x_1,\dots,x_{10}$ given that $\sum_{i=1}^{10} x_i \leq 7$. How do we solve the following problem?
$$
\begin{equation}
\begin{...
- 11
1
vote
0
answers
20
views
Running time of 01-Knapsack-like with negative weight/values, absolute value weight constraint, and volume constraint?
Background
In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of $n$ items where item $i$ has weight $w_i\in\mathbb{N}$, volume $u_i\...
- 153
0
votes
1
answer
75
views
Solve modified knapsack problem using dynamic programming
I'm trying to solve following modified knapsack problem using dynamic programming.
What we know:
Total number of items
Item weight, value and type
Knapsack capacity
Aims
Find Maximum weight of ...
- 1
1
vote
1
answer
46
views
Subdivide a graph into non-crossing triangles with maximum edge weight
Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum ...
- 293
-1
votes
1
answer
66
views
Largest number of disjoint paths of length $k$ and maximum reward in a tree
Consider exercise 23(c) of chapter "Greedy Algorithms", Algorithms by Jeff Erickson.
Given a tree $T=(V,E)$ in which each node has a reward, and
$k\in\mathbb{N}$, our goal is to find a set $...
- 1
0
votes
2
answers
126
views
Dynamic Programming - Difficult Jumping Frog Problem
Given a set of $n$ stones, arranged in a row at equal distances from each other. The stones are numbered from $0$ to $n-1$. A frog that is on stone number $0$ has to get to stone number $n-1$.
A jump ...
- 71
1
vote
1
answer
36
views
Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?
In the Optimal Substructure Wikipedia,
As an example of a problem that is unlikely to exhibit optimal
substructure, consider the problem of finding the cheapest airline
ticket from Buenos Aires to ...
- 173
0
votes
2
answers
65
views
Find the largest MinHeap subtree in a given Tree
We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
- 21
1
vote
0
answers
47
views
The Longest Sequence of Blocks
We have n block $B_i$ $(1 \le i \le n)$, each block has 6 faces and each face material, is one of the k types (k is an input parameter).
In addition, each block $B_i$ has the weight $W_i$.
the ...
- 21
0
votes
0
answers
41
views
Optimal substructure
Is optimal substructure lost when there are different functions in the recurrence relation?
Does optimal substructure require the construction of its solution only from subproblems of the same ...
- 145
2
votes
2
answers
106
views
Factor a number in the longest possible product of distinct numbers
I got stuck with quite a simple problem:
Given a positive number $X$ find the largest number $k$, for which exists the positive distinct integers $Y_1,…,Y_k$ such that $(Y_1+1)(Y_2+1)⋯(Y_k+1)=X$
Any ...
- 121
1
vote
0
answers
44
views
Text Justification problem of "Introduction to algorithm"
The problem that I currently went through is kind of text justification problem. The problem is given that there is a paragraph and a some blank lines. We want to print this paragraph neatly on the ...
1
vote
0
answers
75
views
Why are these two recurrence relations that compute the shortest path equal?
Given a directed graph $G=(V,E)$ with positive weight function $w$, source $s$, destination $t$ and a nonnegative integer $\ell$, we want to find shortest path $\pi$ from $s$ to $t$ such that $\pi$ ...
- 1
4
votes
1
answer
55
views
Non adjacent sum: Why do we need to include or exclude the current element?
The problem goes like this:
Write a function, nonAdjacentSum, that takes in an array of numbers as an argument. The function should return the maximum sum of non-adjacent elements in the array. There ...
- 143
1
vote
1
answer
39
views
Is there a way to determine the LCS of three based on the LCS-s of all three pairs?
Let $\Sigma$ be an alphabet of some symbols, and let $\mathrm{lcs}$ denote the length of the longest common subsequence of two or more sequences defined on $\Sigma$. For some $A,B,C\in\Sigma^{\star}$, ...
- 111
2
votes
1
answer
90
views
(Leetcode; Dynamic Programming) Partition to K Equal Sum Subsets memoization
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
This is leetcode problem #698.
Below is code that I ...
- 123
0
votes
0
answers
21
views
Knapsack problem with fractional weights
I was thinking about whether there is a polynomial solution for a knapsack problem with fractional weights. For example, your goal is to maximize the total value of the items subject to the ...
- 101
-1
votes
1
answer
40
views
Are there a Dynamic programming solution that partition number and minimize the sum of absolute difference of each partition?
Suppose given $n=2k$ numbers. We want partition numbers into two group $G_1,G_2$. Let $d_1$ be the largest value of absolute difference between each pair of numbers in $G_1$ and also $d_2$ be the ...
- 1
2
votes
2
answers
42
views
Programmatically determine if a tie is possible in US elections
Problem 3.5 from book: "Algorithms for interviews".
There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here
Suppose there are ...
- 123
4
votes
0
answers
146
views
Find a dynamic programming solution that minimize the sum of the diameters of two clusters?
I asked a question at this link, where I suggested a greedy algorithm for this problem:
Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
- 1
2
votes
0
answers
44
views
Algorithm for half-sample mode better than O(N^2)
The half-sample mode is a mode estimator that homes in on the highest density region of a set of samples in search of the mode. It is one of the better mode estimators, though it fails for J-shaped ...
- 181
0
votes
0
answers
43
views
Is this partition problem NP-complete?
Problem description:
You are given an integer array Inventories representing the ribbon
inventories, where Inventories[i] represents the length of the ith
ribbon, and an array of orders. Each order in ...
0
votes
0
answers
32
views
Transform binary tree to max heap with minimal number of key changes
I am stuck on this interview practice problem and could use some advice. Given a binary tree, assume that you are only allowed to change the values of the keys of the nodes so that the Max Heap ...
2
votes
1
answer
78
views
most cost-effective route w.r.t. gas in a labelled graph
Consider a car that can hold gas to travel a distance of $c \in N$ kilometers (its capacity) on a full tank that's initially empty. The car starts in node $s \in V$ of a graph. Each vertex $V_i$ of ...
- 2,375
0
votes
1
answer
76
views
Is there a solution faster than O(n^2) for this greedy/sorting problem?
In a market there are N different items where each item is unique and identified by id (1-N). There are also K buyers with names (1-K). Each buyer has 2 items that they want to buy (A, B), where A is ...
- 21
1
vote
0
answers
45
views
Most Likely Number of Winners - Dynamic Programming
You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Give a dynamic programming algorithm that returns the most ...
- 11
0
votes
1
answer
179
views
Bellman ford shortest paths with at least k edges
I was able to understand the problem of at most k edges and exactly k edges but I am not able to wrap my head around how do I solve the problem of getting shortest paths with at least k edges. You can ...
- 3
0
votes
0
answers
30
views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
- 456