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
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 ...
user avatar
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 ...
user avatar
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} \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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(...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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&...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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, $\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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', ...
user avatar
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 ...
user avatar
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{...
user avatar
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\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
  • 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}$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
18