# 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
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[]...
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 ...
• 5,311
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 ...
• 478
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 ...
• 2,489
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 <...
• 3,490
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: ...
• 171
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. ...
• 265
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 ...
• 2,396
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 ...
• 31
262 views

### Longest Palindromic Substring | Python Code Giving TLE

Problem Statement Given a string s , return the longest palindromic substring in s. Constraints ...
• 138
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'. ...
370 views

### Bursting Balloons

This is a Leetcode problem - Given n balloons, indexed from 0 to n-1. Each balloon is ...
• 2,489
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 ...
• 121
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 ...
• 171
1k views

### minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
• 737
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 ...
• 2,396
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 (...
• 21
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 ...
• 2,934
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 ...
1 vote
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: ...
• 111
1 vote
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. ...
• 21
1 vote
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 ...
• 111
1 vote
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 ...
• 5,311
1 vote
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-...
• 161
1 vote
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 ...
1 vote
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. ...
• 203
1 vote
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 ...
• 19
1 vote