Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems. Do not use this tag for general "dynamic" behavior in code.
5,268
questions
-1
votes
0
answers
15
views
What is wrong with the dynamic Programming state
I was trying to solve the problem where if I was given an array of int which allows duplicate, I need to find the count of how many permutation of this array there are such that each adjacent pair of ...
0
votes
0
answers
8
views
Maximal sidelength of a square containing a point and intersecting no other square
Given a list of squares L, each embedded (non-overlapping) in an n x n grid, I would like to find the sidelength of the largest square which contains an given position (i,j) and does not intersect any ...
1
vote
1
answer
30
views
Maximum non negative product in a matrix
I am trying to solve the following problem on leetcode.com
I found a resource asking a similar question but it didn't yield anything plausible.
I am able to come up with a recursive backtracking ...
1
vote
1
answer
19
views
Failing to see the difference between these two lines of thought in dynamic programming
Always there are multiple ways people describe differences in tabulation and memoization in dynamic programming, but I will summarize to what is normally said.
memoization is a where we add caching ...
-3
votes
0
answers
22
views
Given a string of digits, return all ways to sum to a target. (interview question)
Given a string of numbers, s, return all the ways to insert "+" or "-" in between the numbers in s such that the result sums to target.
Example 1: s = "11111", target = 4
...
0
votes
1
answer
25
views
Update the Nested Json with another Nested Json using php
I am new to PHP and have little experience with PHP arrays. I have the nested JSON data and I want to update some data with new data by the field id. I am trying to create dynamic sections with fields....
-1
votes
0
answers
18
views
Showing TLE during submission
question link: https://practice.geeksforgeeks.org/problems/subset-sum-problem-1611555638/1/#
if(sum == 0){
return true;
}
if(n == 0 && sum > 0){
return false;
}
if(arr[n - 1] <= ...
0
votes
0
answers
30
views
confused about dynamic programming state
I was trying to solve the problem where if I was given an array of int which allows duplicate,
I need to find the count of how many permutation of this array there are such that each adjacent pair of ...
1
vote
2
answers
80
views
How can I improve its runtime
Problem Statement: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that ...
0
votes
0
answers
24
views
Greedy vs Dynamic Programming to find split of even integers
I was solving the common coin change problem and it makes sense to solve using DP, since the greedy approach won't work here. Eg. For amount 12, if coins = {3,5} then greedy algorithm to use minimum ...
2
votes
0
answers
94
views
Organizing shipping containers with recursive dynamic programming
I'm trying to solve the following problem using Recursive Dynamic Programming:
Given a shipyard of width W, M cranes to haul containers onto the yard and N shipping containers of varying sizes (<W),...
1
vote
0
answers
51
views
Print all paths of 1s from top left to bottom right cell in a matrix
You are given a 2-D matrix with M rows and N columns.You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right (R) or downwards (D). The array ...
1
vote
0
answers
20
views
Need help in figuring out bug in Word Wrap problem DP solution
The problem statement is given here : https://practice.geeksforgeeks.org/problems/word-wrap1646/1#
This it the solution I came up with.
class Solution
{
public int solveWordWrap (int[] nums, int k)...
0
votes
1
answer
65
views
Top-down approach poorly implemented
I have been kinda practicing some recursive / dynamic programming exercises, but I have been struggling trying to convert this recursive problem into a top-down one, as for example, for f(4,4), the ...
0
votes
5
answers
3k
views
Maximum Sum of Two Non-Overlapping Subarrays of any length
I see "Maximum Sum of Two Non-Overlapping Subarrays (of specific given lengths and the array contains only positive numbers)" from Leetcode
https://leetcode.com/problems/maximum-sum-of-two-...
0
votes
2
answers
61
views
Splitting Array Into Partitions Whose Individual Sums Cannot Go Above X
The task is to design an algorithm that partitions the numbers (a1, a2, .... ,an) in the same order as they appear in the array into the following partitions:
A1= (a1, .... , aj), A2= (aj+1, .... ,ak),...
-1
votes
0
answers
19
views
Maximum Subarray - Dynamic Programming (Top Down)
Can anyone explain to me why we are forcing max() to take zero.
Can't we only call with
if(mustPick)
return dp[mustPick][i] = **A[i] + solve(A, i+1, true, dp)**;
Code:
class Solution {
...
0
votes
0
answers
24
views
Is it possible to do dynamic programming from row to row within window function in PostgreSQL?
Take fibonacci sequence for example:
SELECT
LAG(rolling) + input_value OVER (PARTITION BY 1 ROWS UNBOUNDED PRECEDING) AS rolling
FROM (
VALUES
(1),
(2),
(3),
(4),
(5)
) ...
0
votes
0
answers
35
views
Double Increasing Series relation explanation
I was solving this question : https://www.interviewbit.com/problems/double-increasing-series/
Basically the q is :
Given two integers A and B.
Find the number of sequences of length B, such that every ...
0
votes
0
answers
51
views
please help me in finding all the counts of beautiful permutation
With an array consisting of integers where each integer occurs at most 2 times in the array, I have to count the number of beautiful permutations.
A permutation is beautiful if there is no index i ...
0
votes
0
answers
24
views
Knapsack Dynamic Programming - Need help on problem (Roller Coaster Fun)
I recently started learning Dynamic Programming, and am currently trying to solve "Roller Coaster Fun" on Kattis. However, I'm only getting 10/30 test cases (wrong answer on test case 11), ...
0
votes
0
answers
28
views
Dynamic programming - Gold mine grid optimization TLE
I'm trying to solve Gold Mine problem from https://practice.geeksforgeeks.org/problems/gold-mine-problem2608/1/#. I am receiving TLE for the following code. I have looked at the solution also yet dont ...
0
votes
1
answer
93
views
How to write an algorithm to find maximum possible weight of a package
I need to find the maximum possible weight of a package that can be achieved after any sequence of merge operations:
Below is the use case:
Consider n packages, where packageWeight[i] represents the ...
0
votes
0
answers
23
views
Length of Longest palidromic substring
The below code gives right answer for Longest palidromic subsequence length.How can i modify the code to get Longest palidromic substring?
My code fails when input is s = "abca".Answer ...
-1
votes
0
answers
23
views
dynamic programming grid problem approach solving using BFS in python
enter image description hereUpload your executable code here to the following algorithm problem statement: We have an NxM grid, grid have one element named Bob. Bob can travel diagonally blocks only. ...
0
votes
0
answers
43
views
Print longest Palindromic substring
I have written the below code to find the length of longest palindromic substring which returns correct result.
I want to recover the value of longest substring .How can i do it?
String s ="...
0
votes
2
answers
61
views
Freeing memory space when deleting a node in a circular LinkedList without declaring a new pointer
I've come across a problem in dynamic programming in which we are asked to delete nodes of a circular LinkedList, in the following manner.
Delete the first node then skip one and delete the next, then ...
1
vote
2
answers
34
views
confusing question of maximum possible weight of a subsequence
The weight of a sequence a0, a1, …, an-1 of real numbers is defined as
a0+a1/2+…+ aa-1/2n-1. A subsequence of a sequence is obtained by
deleting some elements from the sequence, keeping the order of ...
0
votes
1
answer
38
views
0-1 knapsack TLE
I was solving 0-1 knapsack problem (src:https://www.interviewbit.com/problems/0-1-knapsack/)
and would like to understand why I got TLE and know how to get rid of TLE .
My solution : (which showed TLE ...
0
votes
1
answer
20
views
Getting this issue in Dynamic Programming using memoization
I am working on the Dynamic programming concept using Python. I have designed a simple code that for for each recursion it divides the given input (n) by 2 and add in the memo dict. I want the memo ...
-1
votes
0
answers
54
views
LeetCode: Best time to buy and sell a stock: Time efficiency factor
I have two solutions to solve this problem. The slower one that takes 1600 milliseconds is my solution while the second one that takes 900 milliseconds is from the forum. My solution is very very slow,...
0
votes
2
answers
67
views
LeetCode question : House Robber II The code does not return correct output
The link to the question is here : House Robber II
I've solved House Robber using the code below and it is absolutely correct:
class Solution {
public int rob(int[] nums) {
int[] dp = new ...
0
votes
0
answers
48
views
How to set dynamic position of snackbar in jetpack compose?
I have a Scaffold with a NavHost as its content. NavHost host 2 screens. One screen contains the bottomNavigationBar and another screen doesnot.
How can I display create a snack bar that can be used ...
0
votes
1
answer
34
views
How can you solve this kind of algorithm problem? (The set purchasing problem-solving)
I just saw a kind of algorithm problem like the one below. I don't know how to solve it efficiently so I want to listen to your opinion.
The problem is that you should find the cheapest price to buy ...
0
votes
1
answer
53
views
Longest Increasing Subsequence. Why topDown code is not working working?
Q. Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without ...
2
votes
1
answer
80
views
Count Combinations in the given String using Dynamic programming
I found an exercise in the "Algorithms and Data Structures" book that I'm unable to solve.
Starting with a table of characters encoding:
| left | center |
|:---- |:-------|
| A | 0 |
...
-4
votes
0
answers
62
views
How to solve a coin change related problem(DP)
In Coin Change 2 , the number of given different coins is unlimited, and the goal is to Return the number of combinations that make up a specific amount.
And what i am gonna do is to let the number of ...
1
vote
1
answer
23
views
Difference in Outputs of classical knapsack problem [duplicate]
I wrote a program for a classical knapsack problem and it is working good.
Below is the code:
class Solution:
def knapsack(self, wt, val, crr_cap, n):
if crr_cap == 0 or n == 0:
...
0
votes
1
answer
55
views
How can I return the turbulence sequence with a complexity of O(n)?
#include <iostream>
#include <utility>
using namespace std;
pair<int,int> findLongestTurbulence(int arr[], int n){
pair<int,int> ret = {0,-1};
int a = -1;
for(...
0
votes
1
answer
15
views
Dynamic programming efficient network
Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting node to ending, with the constrain that the vertices and edges will have an equal or ...
2
votes
1
answer
62
views
How to solve M times prefix sum with better time complexity
The problem is to find the prefix sum of array of length N by repeating the process M times. e.g.
Example N=3
M=4
array = 1 2 3
output = 1 6 21
Explanation:
Step 1 prefix Sum = 1 3 6
Step 2 prefix sum ...
0
votes
0
answers
33
views
Cannot find a solution for a budget expenditure maximisation problem
I am trying to solve a DP problem which consists on the following:
Let's say that we are a town hall with a budget B and have a set of projects P, each one with a cost p_i to build. Since the town ...
-1
votes
0
answers
29
views
Stuggling to develop progeam for variation of coin change problem with limited coins
I have the same problem as:
Coin change problem: limited coins, interested in number of unique ways to make change
However I am unable to determine how to create a solution based on the answers ...
0
votes
0
answers
14
views
Dynamic SQL to find multiple levels of hierarchical substance in SAP
Problem statement : I have parent substance (BE8588). I need to find out substances across all the levels this parent element can be related to. My query currently is giving only until the first level ...
-1
votes
0
answers
20
views
in a row and column wise sorted 2d matrix , how to replace an element with INT_MAX and maintain the order
in the above image, we have matrix that is row and column wise sorted but there is no guarantee of the last element of the previous row being smaller than the first element of the current row.
we need ...
1
vote
4
answers
75
views
What is the best algorithm to get maximum total value in binary tree?
I have some questions about getting maximum sum value in binary tree.
Each node can have two child nodes (Left, Right)
Sum[7, 3, 8, 7, 5] is the maximum sum value for the example above.
First, I ...
0
votes
0
answers
24
views
Android Studio Display code although it is not completely executed
I want to see how my spiral forms in my device. However, it will only show me the result if the code is executed completely and not only the single steps. Is there a way to change it, so that I can ...
1
vote
1
answer
69
views
Why is my code giving time-limit exceeded while a near identical code works just fine in LeetCode?
Ref: https://leetcode.com/problems/word-search/submissions/
Brief problem statement: Given a matrix of characters and a string, does the string exist in this matrix. Please refer the above link for ...
0
votes
0
answers
32
views
AddressSanitizer:DEADLYSIGNAL?
I am getting this error
AddressSanitizer:DEADLYSIGNAL
=================================================================
==32==ERROR: AddressSanitizer: stack-overflow on address 0x7fff4d8f4ff8 (pc ...
1
vote
1
answer
51
views
Find the mimimum positive multiplicative path through an array
I want to solve the following problem using a dynamic programming algorithm (if possible):
Given a square matrix/array A of non-negative integers of any arbitrary size NxN, the objective is to find a ...