# Questions tagged [dynamic-programming]

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

298 questions
Filter by
Sorted by
Tagged with
1 vote
835 views

### Compute the number of ways a given amount (cents) can be changed

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented. My code appears to work (although I am curious to ...
1k views

### Counting subsets with sum not exceeding some limit

I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ...
• 133
485 views

### HackerRank Equal with Scala

For studying Scala, I wrote some code to solve the Equal problem on HackerRank. But I am stuck on test case #15 due to timeout. Christy is interning at HackerRank. One day she has to distribute ...
1 vote
110 views

• 3,453
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
269 views

### Assembly Line Scheduling challenge, solved using TDD

I am new to Test Driven Development and currently practicing it with some problem statement. Following is an Assembly Line Problem statement I solved using TDD approach in java. Please provide me some ...
431 views

### Different path for grid move

Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points. My major idea is, if move r steps right, <...
• 3,453
108 views

### Given two words, transform the first one into the second [closed]

As the title says, the problem I had to do sounded something like this: We are given two words, S1 and S2. We must transform S1 into S2, using the following operations: insert: insert a character in ...
• 31
1 vote
284 views

### SPOJ - Alphacode - Exceeds Time Limit

I'm trying to solve Alphacode on SPOJ. The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26. It works fine for small ...
• 189
1k views

### Dynamic attribute key selector

I'm basically trying to build a function that searches all nodes on the DOM to check for data attributes, then swap them out with whatever is stored with the "data-intl-" attribute. For example, if ...
• 93
1 vote
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 ...
• 21
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
570 views

### Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...
616 views

### Justify text from a file using a LaTeX method

I wrote a bit of code that takes a file, justifies the text and writes to another file. It uses a DP approach to minimise a badness metric, which is the amount of undershoot of the line length, cubed ...
• 2,373
497 views

### Python graph challenge

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
• 73