Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
923
questions
0
votes
0
answers
14
views
Formulating a bottom-up dynamic programming premise for a board game
The game being played here has the following rules, played be a singular player: there is a 5x5 board, where some tiles are highlighted and some are not. From here, the player can highlight the blank ...
- 1
1
vote
0
answers
33
views
Dynamic Programming: Counting *cycles* consisting of distinct numbers
I was thinking about this question and thought about it for quite a while but couldn't come up with an answer.
Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
- 111
0
votes
1
answer
19
views
Distinguishing Between Two mixed integer Programming Problems: Is Concavity of the Price Function the Key Difference(besides the cost of backlogging)?
I've been examining two mixed integer programming problems presented in two different papers. I've noticed some similarities between them but I'm having trouble distinguishing the key differences.
...
- 1
0
votes
0
answers
24
views
Optimality in greedy task
There is a well-known problem of the best time to buy and sell stock. Assume now we have two arrays, SELL and BUY. Each time SELL[i] > BUY[i]. Assume we have initial budget B, and we can buy any ...
- 151
1
vote
2
answers
39
views
Zero sum game: dp recursion strategy
Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
- 111
0
votes
1
answer
44
views
How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem.
I have elements from 1 to n and I am trying to cover all of the elements using the ...
- 11
0
votes
0
answers
30
views
House Robber Problem Variation with Risk/Cost to Rob Each House
I came across a modification of the classic house robber problem where there is a cost to robbing each house, and we want to maximize the amount robbed using the array (exactly as in the original ...
1
vote
1
answer
27
views
Constrained precedence parsing
This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem?
The setup is as follows: we are given $n$ ...
- 531
0
votes
0
answers
27
views
Algorithms for finding number of sequences with length N and displacements less than k
The sequences are made up of only digits. A displacement is defined as pair $(i, j)$ such that $i > j$ and $A[i] < A[j]$. For example, 423 has 2 displacements.
The question is to find the number ...
0
votes
1
answer
55
views
Why does the non-adjacent sum problem have optimal substructure?
In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $[1,4,3,8,5]$ the largest sum of non-adjacent ...
- 1
-2
votes
1
answer
57
views
Find Number of subsequences such that bitwise OR is same as sum
Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
- 1
0
votes
0
answers
26
views
Upper bound of traveling salesman problem via dynamic programming
For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be
\begin{equation}
\sum_{k=1}^{n-1} O\left(\left(\begin{...
- 101
0
votes
0
answers
26
views
Is there a sorting program or formula to sort and place individuals in classes based on preferences
I am looking for a formula or program to help place people in classes based on their preferences.
The elements of the problem are:
There are 30 class choices a student can pick from.
There are 400 ...
- 1
1
vote
1
answer
87
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
2
votes
1
answer
34
views
Checking forbidden moves in Renju
I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works.
Renju is a board game played on a 15x15 Go board. There are two players in the ...
2
votes
0
answers
59
views
Recurrence Relation for Longest Increasing Subsequence Problem
I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
- 21
2
votes
2
answers
399
views
Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals.
Note that there are 2 cases ...
- 123
1
vote
2
answers
75
views
How do I find the most even combination for two arrays
I have two arrays that both contain n elements (positive,non zero, not negative)
{x1....xn}
{y1....yn}
I want to pair them up optimally, one from each array, so that the pairs come out as even as ...
- 11
0
votes
1
answer
55
views
Compute the maximum length of an increasing digital subsequence given an array of digits
Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson.
Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
- 1,554
1
vote
0
answers
129
views
Tabular Meta-Learning in RL
There are various meta-learning algorithms in RL that are proposed for settings when we have a (deep) neural network and the policy (or the value function) are parameterized as such.
Can these methods ...
- 175
0
votes
1
answer
47
views
Confused on Bellman Ford
We have a graph where we want to get from node u to v in the shortest path possible.
I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
1
vote
1
answer
77
views
Another Game Theory Problem
We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
- 25
0
votes
0
answers
36
views
Is there always a Dynamic Programming Solution underlying a greedy solution to any algorithmic problem?
According to CLRS book, Introduction to Algorithms,
Nevertheless, beneath every greedy algorithm, there is almost always a
more cumbersome dynamic-programming solution
As the word "almost" ...
1
vote
0
answers
61
views
Find maximum number of vertex-disjoint paths of length $k$ in a tree with no restrictions for the paths
I am working currently on Path-Packing problems and found this Book:
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
My question is about exercise 23b on page 184.
Here is ...
- 11
0
votes
0
answers
16
views
Changing the order of assignment in a state machine algorithm for Best Time to Buy and Sell Stock problem
Here's a smaple solution to Best Time to Buy and Sell Stock III problem:
...
- 101
2
votes
1
answer
60
views
Is this varient of longest increasing nested sets problem NP-hard？
There are two types of sets $\mathcal{X} = \{X_{1}, X_{2}, \ldots, X_{n_{1}} \}$ and $\mathcal{Y} = \{Y_{1}, Y_{2}, \ldots, Y_{n_{2}}\}$ such that $X_i, Y_j \subseteq [m]=[\mathrm{poly}(n)]$ and $n = ...
- 613
-1
votes
2
answers
365
views
Longest increasing subsequence when a number can be added to all numbers in a subarray
A sequence $(a_1,a_2, \dots, a_n) $ and natural numbers $n$ and $k$ are given.
We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...
- 37
0
votes
1
answer
133
views
What is the best way to solve the coin change problem using dynamic programming?
I have found two ways of applying dynamic programming to the coin change problem of finding the minimum number of coins from a given set of denominations to make a given sum. I wanted to know if one ...
- 111
0
votes
1
answer
48
views
Given a list of pairs (cost,points) and a number k, find the maximum sum of points with sum of costs less than or equal to k
Given a list of $n$ pairs (cost,points) and number $k$ ($0 \le k$), find the maximum possible sum of points s.t their sum of costs no more than $k$. return the maximum possible sum of points and their ...
- 228
1
vote
1
answer
94
views
Finding minimal moves to move boxes into m floors
Assume a tower with $n$ floors.
Each floor contains $C_i$ boxes such that $C_i>0$ for all $1\le i\le n $
Moving $C_i$ boxes from floor $i$ to floor $j$ where $i>j$ costs $C_i\cdot(i-j)$ and we ...
- 212
1
vote
0
answers
17
views
Optimal expression ordering with short-circuit evaluation [duplicate]
Let $E_1, E_2, \ldots, E_n$ be boolean-valued expressions, each with an associated evaluation cost and probability of returning true. For simplicity, assume these ...
- 105
0
votes
0
answers
49
views
Finding the diameter of a N-ary tree graph, without using BFS
As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.
This must be done in linear time.
The problem states that the graph is undirected ...
- 316
-3
votes
1
answer
41
views
Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?
Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums ...
1
vote
1
answer
559
views
Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
- 316
1
vote
1
answer
106
views
Single machine scheduling with profit and deadline constraints
The problem is described as such:
Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’.
So for some $i \in \{1,\ldots , n\}$, $J_i=\{t_i,p_i\}$ where $t_i$ is the ...
- 316
1
vote
1
answer
36
views
Heterogenous Resource Allocation Using Dynamic Programming
I'm working on a resource allocation problem, where there are $n$ different Items and $m$ different tasks ($n\geq m$). Also, The profit of assigning subset $I=\,(\, |I|\leq n)$ of items to task $j$ is ...
- 11
0
votes
0
answers
32
views
How to compute a closed form solution of Hamilton-Jacobi-Bellman equation?
The following paper provides a HJB equation and its closed form solution for a special case.
https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/3943/vanryzin_optimal_dynamic_pricing.pdf
...
- 113
0
votes
2
answers
115
views
Time complexity of finding the minimum by dynamic programing
How can I calculate the complexity of computing $MD(b)$, where $b=(b_1,b_2,\dots,b_n)$?
$$MD(s) = \max(s)-\min(s) + \min(MD(s\setminus\{\max(s)\}), MD(s\setminus\{\min(s)\}))$$
where $s$ is a finite ...
- 37
0
votes
1
answer
43
views
Maximal Profit of 'legal' cutting of a board
I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.
Given a board of length $n$, and an increasing ...
- 316
-1
votes
1
answer
49
views
how to find the most optimal path for this problem?
There are N islands and there is one pirate. The pirate can start out from any one of the n islands and has the option of either staying on the same island for the next day or moving to a different ...
- 1
0
votes
1
answer
41
views
maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$
Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
- 101
-3
votes
1
answer
95
views
how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000
how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000
for example for n=3, there is 15 solutions
1^1=1^1
1^1=1^2
1^1=1^3
1^2=1^1
1^2=1^2
1^2=1^3
1^3=1^1
1^3=1^2
1^...
1
vote
1
answer
105
views
Is there an efficient way to solve this problem?
Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k.
Note that the series does not ...
- 13
0
votes
3
answers
133
views
is there an O(n^2) approach to this problem?
Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by:
(left boundary point - right boundary point of the ...
1
vote
1
answer
89
views
What is the proper way to approach a competitive coding problem?
***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/
1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering ...
0
votes
0
answers
30
views
Maximum Accumulated Balance after Purchasing Machines
A company is able to earn x dollars per day without any machines. However, there are n machines available for purchase. The <...
- 11
0
votes
0
answers
76
views
Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)
Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method?
Recurrence formula from CLRS book
When n = 1, the sequence consists of just one ...
0
votes
0
answers
225
views
Binary Matrix covered with squares to cover all 1's in min cost
So I recently came across a question in my Algorithms class.
Given a binary matrix of N X N.
we can do following operation any number of times
we can take a square of size M X M (1 <= M <= N) ...
5
votes
2
answers
2k
views
Why does the order of the nested loops matter when solving the Coin Change problem?
The Coin Change problem is stated as:
Given an integer array coins[ ] of size N representing different
denominations of currency and an integer sum, find the number of ways
you can make sum by using ...
- 161
0
votes
1
answer
20
views
Algorithm to optimise the cost to choose a subset of array
I have been on this problem for very long time, Lets assume we have a shopping list eg:{milk,bread,coke,orange,apple,..} and the shop only sells pack of thing and ...
- 157