Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
713
questions
1
vote
1answer
10 views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
2
votes
0answers
29 views
Relationship between dynamic programming and reinforcement learning
I wasn't sure whether to post this here or in the ai stack exchange - please let me know if i need to move my post elsewhere)
I have been learning about how dynamic programming can be used as a tool ...
1
vote
0answers
21 views
Find exact sum in path
So the question is
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
0
votes
0answers
37 views
Two-Sum Algorithm Design - Pre-sort, Range Allowance, Many Sums
𧩠Design Questions
I would love feedback on the pseudocode design outlined in the section below and if each design is an optimal approach in terms of runtime complexity?
Pre-Sort: Is it possible to ...
1
vote
1answer
41 views
Minimum sum of squared Euclidean distance between two arrays
Question:
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the ...
1
vote
1answer
89 views
Fastest Algorithm for Computing Expected Value [closed]
I came across this interesting problem:
If π is a finite binary string consisting of just 1's and 0's, then denote π(π) as the sum of the squares of the lengths of the consecutive runs of π. For ...
-1
votes
0answers
18 views
C programming pointer topic [closed]
Write a program to find the
sum of all non-prime numbers
from m and n (including m and
n also) using the concept of
passing pointers to function.
Pass addresses of m, n and sum
integers from the main (...
0
votes
1answer
51 views
approaching dynamic programing for problem
I want to find a solution to a problem that asked before.
in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-...
1
vote
0answers
60 views
Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming
If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \...
0
votes
0answers
39 views
Algorithm design to partition a set of students [closed]
I'm learning algorithm design and I saw this problem: Problem: We have n students in (numbered from 1 to n). Students need to be divided into group for in-class activities. Each student has a ...
1
vote
1answer
23 views
Generating all the increasing subsequences
Given an array of integers, how can we generate all the increasing subsequnces of length of 4 ?
Example: given this list
l = [1, 2, 4, 5, 3, 6]
The answer should ...
0
votes
2answers
69 views
Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?
Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but ...
1
vote
2answers
30 views
About the pseudo polynomial complexity of the KnapSack 0/1 problem
I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
0
votes
0answers
15 views
Probability that BST has exact height
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
...
0
votes
0answers
23 views
Number of complete traversals of the circle in generalised Josephus problem?
In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (...
1
vote
1answer
21 views
Unconstrained subset sum vs constrained subset sum?
In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: ...
0
votes
1answer
58 views
For dynamic programming problems, how do we know the subproblems will share subproblems?
So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:
...
2
votes
1answer
37 views
0-1 Knapsack problem with item discounts
I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
1
vote
1answer
52 views
Recurrence formula for optimal binary search tree
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For ...
0
votes
1answer
50 views
How is equation 1 simplified to equation 2 as shown below
In CLRS (Intro to algorithms) on page 362, it says eqn(1) :
can be simplified to this equation(2):
I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
1
vote
1answer
37 views
Does this LCS algo generate all the CS or only all the LCSs?
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
0
votes
0answers
30 views
Optimal partitioning of n-arrays
You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.
The goal is to partition those arrays into K ...
1
vote
1answer
108 views
Linear Grammar in less than cubic time
I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ ...
0
votes
0answers
47 views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
1
vote
0answers
32 views
Algorithm to Check for Upper Bound of Levenshtein Distance
I am looking for an algorithm that checks if the Levenshtein distance between two strings $s_1$ and $s_2$ is less than a certain upper bound $B$. I know, there are plenty of algorithms for calculating ...
0
votes
1answer
31 views
Interval Scheduling problem with more than 1 machine
There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n ...
1
vote
1answer
113 views
Count subset divisible by 3
I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is ...
0
votes
0answers
25 views
Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?
First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to ...
1
vote
1answer
30 views
Find maximal subset with interesting weight function
You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
2
votes
1answer
18 views
Policy dependent on initial state distribution in finite horizon MDPs
Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition ...
3
votes
0answers
71 views
Speeding up the Rummikub algorithm - explanation required
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
1
vote
1answer
75 views
Longest common sub-sequences with a condition
A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length....
1
vote
1answer
42 views
Count minimum number of steps to destroy all blocks
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the ...
0
votes
1answer
53 views
Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of ...
-3
votes
1answer
53 views
Subset sum problem with a complication
I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them?
The size of my list can be ...
0
votes
1answer
33 views
Determine if there is a subset of the given set with sum divisible by a given integer
I've been given a question to solve:
Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.
For this question the ...
5
votes
2answers
142 views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
1
vote
0answers
37 views
Choosing a method for algorithmic problems - is it an art or science?
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
0
votes
2answers
43 views
Schedule Optimization With Priority and Weighted Costs
I need an algorithm to determine the best itinerary for a series of events.
Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each ...
0
votes
1answer
49 views
Dynamic Programming - Tiling Question
I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
2
votes
1answer
55 views
Probability of winning a turn-based game with a random element
I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.
Given a bag, which contains some given amount of white stones $w$ and some given amount of ...
1
vote
1answer
82 views
Minimum number of given operations in order to group letters in a string
Description
Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
0
votes
1answer
52 views
Distribution of resources from providers to maximum number of receivers
Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what ...
1
vote
1answer
150 views
Bellman Ford Dynamic Programming
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so ...
2
votes
1answer
69 views
Finding all partitions of a grid into k connected components
I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so ...
-2
votes
1answer
887 views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
0
votes
0answers
44 views
Get the maximum sum of n items below a threshold
Consider a modified Knapsack Problem where:
The number of items to be included is fixed.
The value of each item is equal to its weight.
Therefore, given a set of numbers, a threshold and the number ...
0
votes
1answer
89 views
How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.
...
1
vote
1answer
71 views
How to solve a problem about balancing parentheses with smileys?
I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.
I've been trying to solve it by 3 ...
0
votes
1answer
31 views
What is the difference between these two Edit Distance Algorithm
Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why ...
