Skip to main content

Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
134 views

C++ - Longest Common Subsequence

Link to the Problem Here is my code to compute the length of the longest common subsequence of two integer arrays arr[] and brr[]...
White Tiger's user avatar
3 votes
0 answers
309 views

LeetCode: Stone Game C#

https://leetcode.com/problems/stone-game/ Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones ...
Gilad's user avatar
  • 5,311
3 votes
0 answers
678 views

Split money into every possible combination of coin denominations

Background and objective of the code Based on this Dev.to challenge, I wrote the Python code below (TIO link also available). The task was to return the least number of coins in a given denomination ...
agtoever's user avatar
  • 478
3 votes
0 answers
1k views

Python program to solve matrix-chain multiplication

An assignment at school required me to write a Python program for this task: In the matrix-chain multiplication problem, we are given a sequence of matrices ...
Justin's user avatar
  • 2,489
3 votes
0 answers
2k views

Robot on a Grid: Find a path between two corners with forbidden cells on the road

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
Igor Soloydenko's user avatar
3 votes
0 answers
144 views

Convert top-down subset sum to bottom-up

I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum. My code in Java is as follows: ...
ng.newbie's user avatar
  • 171
3 votes
0 answers
56 views

Number of ways to complete a plan

I worked on a dynamic programming problem. Here is its link. I have to find the number of ways respecting the constraint that user doesn't go to the Gym for two consecutive days. ...
SarahData's user avatar
  • 265
3 votes
0 answers
787 views

Hackerrank: Sherlock and anagram (optimal time complexity)

Problem statement Given a string \$S\$, find the number of "unordered anagrammatic pairs" of substrings. Input Format First line contains \$T\$, the number of testcases. Each testcase ...
Jianmin Chen's user avatar
  • 2,396
3 votes
0 answers
97 views

Uses subproblems to solve large problem (maximization of value within space)

If this question is not a good question for this board, I will remove it. I am looking for ideas on how I could improve the code as I am a beginner trying to learn how to program. Here I have a ...
Shezmula's user avatar
3 votes
1 answer
262 views

Longest Palindromic Substring | Python Code Giving TLE

Problem Statement Given a string s , return the longest palindromic substring in s. Constraints ...
Rohit Singh's user avatar
2 votes
0 answers
137 views

Bellman-Ford algorithm implementation

I have used an adjacency list to represent the graph. This implementation is based on the procedure given in the book 'Introduction to Algorithms'. ...
Kushagr Jaiswal's user avatar
2 votes
0 answers
370 views

Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
Justin's user avatar
  • 2,489
2 votes
0 answers
461 views

Smith-Waterman algorithm for local sequence alignment with affine gap penalties

The following is a summary from the top of my head so please correct me if I'm wrong. See the Wikipedia article for more. This is about determining the (score / edit distance of the) most similar ...
ngmir's user avatar
  • 121
2 votes
0 answers
50 views

Optimizations for Knapsack with 3 dimensions

Problem Statement: I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of ...
ng.newbie's user avatar
  • 171
2 votes
0 answers
1k views

minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
noman pouigt's user avatar
2 votes
0 answers
3k views

Hackerrank: Max Score

Problem statement Consider an n-element sequence of integers, A = {a0, a0, ..., an-1}. We want to perform \$n\$ operations on \$A\$, where each operation is defined by the following sequence of ...
Jianmin Chen's user avatar
  • 2,396
2 votes
0 answers
2k views

Word Wrap via Dynamic Programming

Word Wrap problem in short: Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
plethora's user avatar
2 votes
0 answers
405 views

Shortest bitonic tour

This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
MAG's user avatar
  • 2,934
2 votes
0 answers
631 views

Recursive implementation of integer partition without re-arrangement

Problem: Integer partition without re-arrangement Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an integer ...
Daniel Jacobson's user avatar
1 vote
0 answers
36 views

Collecting inputs from a list of file names or stdin if there is no input files

In my program, I want to either read from a file or stdin depending on the arguments. I did this function to collect input: ...
Fayeure's user avatar
  • 111
1 vote
0 answers
69 views

3ph 2l inverter simulation with SPWM

Here is a code for a simple model of three phase two level inverter with constant DC voltage source and three phase RL load. ...
ppinha's user avatar
  • 21
1 vote
0 answers
166 views

Wrapping an ExpandoObject within a SafeExpandoObject

I've written code to deserialize a JSON into an ExpandoObject. The only problem with the ExpandoObject is that if you try to access a member which doesn't exist, it ...
rboy's user avatar
  • 111
1 vote
0 answers
64 views

LeetCode: range sum query mutable c#

https://leetcode.com/problems/range-sum-query-mutable/ I am trying to solve this question using dynamic programming. I guess the guys in leetcode want to limit us to use segment tree or one of the ...
Gilad's user avatar
  • 5,311
1 vote
0 answers
286 views

Divide a set into subset with some constraints

Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here Problem: Given a list Lconsisting of not necessarily unique non-...
xrfxlp's user avatar
  • 161
1 vote
0 answers
126 views

How do I optimize memoization in order to find longest palindromic substring?

I want to find the longest palindromic substring using dynamic programming in Python3. The strings can be as large as this string. I have seen other questions on this problem that successfully solve ...
Aviral Srivastava's user avatar
1 vote
0 answers
2k views

Hackerrank Beautiful Strings

Problem Statement You are given a string, S , consisting of lowercase English letters. A string is beautiful with respect S to if it can be derived from S by removing exactly 2 characters. ...
Rajat Saxena's user avatar
1 vote
0 answers
90 views

selecting 5 best players out of 2 team

Let us assume that we need to develop an application which can select best 11 players to score maximum points. The application will select the best players after completion of a match. The rules are ...
ss321c's user avatar
  • 19
1 vote
0 answers
4k views

Traceback in sequence alignment with affine gap penalty (Needleman-Wunsch)

I am working on an implementation of the Needleman-Wunsch sequence alignment algorithm in python, and I've already implemented the one that uses a linear gap penalty equation for scoring, but now I'm ...
Iocust's user avatar
  • 21
1 vote
0 answers
2k views

DP algorithm to find minimum average wait for customer-serving system

Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
Meena Chaudhary's user avatar