# Questions tagged [dynamic-programming]

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

220 questions
Filter by
Sorted by
Tagged with
578 views

### Hackerrank: Lucky Number Eight (Dynamic Programming)

Problem statement Given an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large,...
83 views

### High execution time on number partitioning program in Python 2.7

I am writing a program to count only the partitions of a number with distinct parts. I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained ...
487 views

### UVA 100: “The 3n + 1 problem”

I’ve solved UVA Problem 100: The 3n + 1 problem . In short, the task was to write a program that calculates a maximum of Collatz sequence lengths for any given range of starting values. My program: <...
198 views

### Dynamic programming solution for cross river algorithm (part 2)

I'm working on the cross river problem (previous post here). Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated. More ...
908 views

### Dynamic programming solution for cross river algorithm

Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style ...
323 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 ...
469 views

### Guess number with lower or higher hints

Problem statement Two players - Alice and Bob. Alice needs to guess a number $n$, from range $[1, N]$, $N \le 200$ In $i$th turn, Alice guesses a number $i$ Bob chooses to ...
83 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 ...
163 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 ...
313 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, <...
94 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 ...
186 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 ...
500 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 ...
2k 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 ...
670 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 (...
337 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. ...
434 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 ...
300 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! ...
882 views

### Repeatedly partitioning an array equally as far as possible

I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases. Nikita just came up with a new array game. The rules are as follows: Initially, ...
419 views

### Longest common substring using dynamic programming

I've written a short python script that attempts to solve the problem of finding the longest common substring using the dynamic programming technique. It is meant to be generalised so I could plug in ...
415 views

### Hackerrank “Bricks Game”

Problem URL This is the solution I came up with the minimax problem stated above. I did a top-down recursive approach with memoization, and I think this should be $O(n)$, since we are filling out a ...
676 views

### Code for calculating best possible combination in an array

The problem here , requires me to find the best possible combination of values in an array which is nearest to 0 and are adjacent to each other , here is an little excerpt from it, The government ...
365 views

### Edit distance implementation

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: In order to transform one source string ...
978 views

### Find the Longest Subsequence using Dynamic Programming

Attempting to learn dynamic programming, it seems like the algorithm works. I'm looking to make sure the algorithm is correct (and actually uses dynamic programming correctly) and for pointers on ways ...
3k views

### Coin change algorithm

I've implemented the coin change algorithm using Dynamic Programming and Greedy Algorithm w/ backtracking. The description is as follows: Given an amount of change (n) list all of the possibilities ...
220 views

### Largest contiguous sub-array sum

Challenge Determine the largest contiguous sum of integers in a list. Specifications The first argument is a path to a file. The file contains multiple lines. Each line is a test case represented ...
2k views

### Obtaining a target number only using the operations ×2, ×3, and +1

Problem Introduction You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal ...
402 views

### Code for calculating number of trailing zeroes after factorial

While trying my hands at the beginner codechef problem I came across this . So basically doing that problem with Dynamic programming is an overkill but why not try that and get some DP practice. Nice,...
2k views

### Yet another Fibonacci number generator

First attempt at dynamic programming. I want to make this run faster and better. fibonacci.cpp ...
958 views

### Change-making problem with specific constraints

I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically? Problem Description: There are n coin denominations, each with an unlimited ...
250 views

### Simple Factor Class

I have a class which lazily factors numbers. It provides the user with these methods: getFactors returns a ...
145 views

### Count the number of ways to obtain a sum, with consecutivity restriction

A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary. ...
319 views

### Number of unique sequences of 3 digits, given a length is equal to sum

This is the "Minion's bored game" problem from Google's "Foobar challenge": There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean. The game is ...
460 views

### Longest Increasing Sub-Sequence using Dynamic Programming in Python

I wrote the following function to find the longest increasing sub-sequence in an array (tuple, it doesn't work for a list since a list is mutable and it stores the results in a dictionary.). It uses ...
305 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 ...
1k views

### Rod-Cutting Problem using dynamic programming

I wrote the following code for solving the Rod-Cutting Problem using dynamic programming: Rod Cutting Problem: Given a rod of length n inches and an array of prices that contains prices of all ...
294 views

### Longest palindrome subsequence

This algorithm finds the longest palindrome that is a subsequence of a given input string in $\Theta(n^2)$. Example Input: character Output: ...
341 views

### google foo.bar max path algorithm puzzle optimization [closed]

I got a programming puzzle described as follows: Save Beta Rabbit Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN grid of rooms. In the center of each room (except for the ...
2k views

### Candie distribution algorithm

I am studying algorithms and I solved this problem under Dynamic Programming section: Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the ...
43 views

I have the following code which loads in a URL based on the id of a user-clicked button. I'm looking to compress it down as much as possible, and make it more modular and reusable: ...
728 views

### High execution time of LCS length program in Python2

I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise. It's quite simple and straightforward, just print out the length of the LCS. I submitted this code: ...
73 views

### Find the best path amongst N random points

For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points. I wanted to use a dynamic ...
2k views

### Levenshtein distance with edit sequence and alignment in Java

I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment: LevenshteinEditDistance.java: ...
363 views

### Number of ways to make change for an amount

Task Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT. My approach The number to make ...
82 views

### Optimally allocating a resource with time-varying demand and cost

I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
817 views

### Auto registering class registry

I built this auto registering registry to look into a package and import all modules and register any classes that are a subclass of a base class. I use it as a registry for a model's choices in ...
2k views

### Finding the longest path, avoiding obstacles in a 2D plane

The Scenario You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
812 views

### Longest contiguous Increasing Subset in java

I have tried to come up with a solution to the longest increasing subsequence problem.Can this solution be optimized further? Example 1: Input: {5,4,3,7,8,9,11} Output: 3, 7, 8, 9, 11 Example 2: ...