Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems which have recursive structure with many overlapping subproblems. Do NOT use this tag for general "dynamic" behavior in code.
dynamic-programming
5,690
questions
1
vote
1
answer
24
views
Maximizing sum of signed numbers by not skipping more than one consecutive value: DP goes wrong
I am trying to solve this code challenge:
A user maintains a list of negative and positive ratings for movies in a collection. The user wants to choose some subsequence of movies from the collection ...
- 11
0
votes
0
answers
12
views
Finding Longest Palindromic Substring, solution is too inefficient but I am not convinced dp is more efficient in this case
I have a solution which is O(n^2).
My idea loop through each character of the given string and find longest possible odd and even substring which results in a palindrome.
Why does my solution take so ...
- 35
3
votes
2
answers
106
views
A more efficient algorithm in finding the number of distinct decompositions a number has using only repdigits
This is a problem from a previous semester that I am trying to upsolve. I am trying to solve a problem involving the total number of ways of decomposing a number using only repdigits. A repdigit is a ...
- 51
-2
votes
0
answers
32
views
Dynamic Programming for Minimum Operations to Equalize Arrays - Incorrect Results
I'm trying to solve a problem where we need to find the minimum number of operations required to make two integer arrays nums and target (same length) equal. In one operation, we can select a subarray ...
- 9,543
-2
votes
0
answers
36
views
There a DP code for question edit distance from CSES problem set and i solved using python in most optimized way but its giving TLE [closed]
import sys
input = sys.stdin.read
def edit_distance(s1, s2):
n1, n2 = len(s1), len(s2)
prev_row = list(range(n2 + 1))
curr_row = [0] * (n2 + 1)
for i in range(1, n1 + 1):
...
0
votes
1
answer
34
views
Performance Comparison Between Tabulation and Memoization for Dynamic Programming [closed]
I'm delving into dynamic programming and trying to understand the general performance differences between tabulation and memoization. Both techniques aim to optimize recursive algorithms by storing ...
- 376
-1
votes
2
answers
96
views
Flip consecutive zeroes to ones in k operations to have maximum number of ones, find the maximum number of ones
You are given a binary string made of 0 and 1, and a value k which represents number of operations. You can flip consecutive 0s in each operation to 1s. Find the maximum number of 1s after k ...
- 23
1
vote
4
answers
81
views
The minimum size of substrings for the presence of at least one character
i have a question that want the minimum length of k that in each consecutive substring of a string with length k, There must be at least one common character.
for example if s="abcaca"
for k ...
- 13
1
vote
1
answer
94
views
Single Source - Single Destination Shortest Path (DFS + DP) - Time complexity?
Context:
I want to write an algorithm for finding the shortest(least cost) path from a fixed source to a fixed destination node in a weighted directed graph with non negative weights (can have cycles)....
- 59
0
votes
2
answers
62
views
Understanding dynamic programming timeouts with 2 different solutions
The problem is from leetcode (link - https://leetcode.com/problems/the-number-of-ways-to-make-the-sum/description/ )
You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with ...
- 5
2
votes
0
answers
48
views
Coin Change Recursive, memoization gone wrong
I'm trying to understand why first one fails and second works, all I'm doing is passing along coinTrack, call it redundant but why does it not work?
It works without memoization, but on using ...
- 333
-1
votes
1
answer
48
views
Coin Change II : To take a value or not to
The problem goes like this:
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of ...
- 5,003
2
votes
4
answers
101
views
Is there a way initialize a matrix(2D array) with some default values(-1)
I was going through a dp problem, there I have to initialize the matrix with default(-1) values for memoized solution. And felt the need.
We can initialize the 1D array in java like this => Arrays....
- 29
0
votes
1
answer
20
views
Recusion: does the order of safety checks vs base cases matter?
I am learning dynamic programming, and I have observed when creating recursive code, sometimes we check out-of-bounds conditions first then check other base cases, and sometimes we check the other ...
1
vote
1
answer
140
views
Asteroid Mining - Dynamic Programming problem
I was given the following assignment:
There is n gram of mineral to be dug up on a certain asteroid. At the beginning there is only one robot at our disposal. Each robot can do one of two activities ...
- 51
0
votes
2
answers
109
views
Dynamic Programming - Minimum cost to fill given weight in a bag
We are given an array of positive weights cost where cost[i] represents the cost of filling i + 1 kg's of oranges in a bag (0-based indexing). We need to find the minimum cost to buy exactly w kg's of ...
- 29
4
votes
3
answers
247
views
Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an n×n Table
We have an n×n table, and in each cell of the table, there is a number from 1 to 2n. We want to change the numbers in some of the cells and replace them with other numbers from 1 to 2n such that in ...
- 41
1
vote
1
answer
62
views
Why backtracking is giving wrong results in case of 1st question and correct results for 2nd. Leetcode #322 #78 respectively
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 you need to make ...
- 31
1
vote
2
answers
129
views
Dynamic programming partition array to find minimum difference fails for negative numbers
I am trying to solve the problem it works for positive integer arrays but fails for negative test cases. How to handle the below test case?
You are given an integer array nums of 2 * n integers. You ...
- 151
0
votes
0
answers
9
views
why this code is giving error in solve_spo function but not in other function use . the solve_spo function is derived from the solve_tabu function
int solve_tabu(int N ,int arr[],int t){
vector<vector<int>> dp(t+1,vector<int>(N+1,0));
for(int i=0;i<=N;i++){
dp[0][i]=1;
}
for(...
0
votes
0
answers
11
views
DynamicProgramming Proble,
Problem Link :https://www.geeksforgeeks.org/problems/count-numbers-containing-43022/1
Problem Description : You are given a number n, Return the count of total numbers from 1 to n containing 4 as a ...
- 1
-2
votes
1
answer
115
views
Coin Change: for loop analysis
I am trying to comprehend the problem which has different wording but I figured it is similar to coin change problem
Question:
Two friends are playing a game with a book numbered from 1 to 9. The game ...
- 43
-2
votes
2
answers
60
views
How to find the optimal products with the lowest price amount with the highest quantity?
I tried to write a function for myself but it somehow incorrectly outputs the final result:
function findOptimalProducts(products, budget) {
const getPrice = (priceString) => parseFloat(...
- 4,882
-4
votes
1
answer
64
views
Why is my code giving wrong answer when using 2d ArrayList and passing when using 2d arrays?
Here is the DP question,
Given a ‘N’ * ’M’ maze with obstacles, count and return the number of unique paths to reach the right-bottom cell from the top-left cell. A cell in the given maze has a value '...
3
votes
1
answer
67
views
Return correct value at each iteration- dynamic programming
The problem goes like this:
Geek is going for n day training program. He can perform any one of these three activities Running, Fighting, and Learning Practice. Each activity has some point on each ...
- 5,003
0
votes
1
answer
21
views
TLE on coin combinations 1 cses
can someone tell why the following code for coin combinations 1 question from cses problemset is getting time limit exceeded
#include <bits/stdc++.h>
#define int long long
using namespace std;
...
1
vote
0
answers
44
views
The principle of solving a problem through dynamic programming
I have the following task, but I don’t understand how I could solve it through dynamic programming or perhaps I need to solve it through graphs, could someone help me solve it?
The frog Sandy likes ...
- 41
0
votes
0
answers
33
views
How can longest strictly increasing subarray problem have overlapping subproblems
In the longest strictly increasing subarray problem, we have an array A, and we need to find the longest subarray such that in that subarray S, S[k]>S[k-1].
Since we can divide the array A into ...
- 1,188
0
votes
1
answer
51
views
Visiting dynamic website and clicking on arrows to expand and then select elements to load the page contents using Python
I am nope in python. I want python to visit this site https://icd.who.int/browse10/2019/en , and click on (arrows to expand them) which are located on this
//tr[@class='ygtvrow']//td[starts-with(@id, '...
0
votes
0
answers
71
views
How to implement join order optimization using dynamic programming in Python?
I am working on a project to optimize SQL queries by determining the optimal join order using dynamic programming in Python.
Context
I am connecting to a PostgreSQL database and need to calculate the ...
