# Questions tagged [dynamic-programming]

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

869 questions
Filter by
Sorted by
Tagged with
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
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 vote
22 views

1 vote
20 views

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
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 ...
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
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
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
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
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
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
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
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
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
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 ...
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
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
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
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 ...
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 ...
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 ...
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
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
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
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 ...