# Questions tagged [dynamic-programming]

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

232 questions
Filter by
Sorted by
Tagged with
786 views

### Regular Expression Matching: Recursive and DP-based implementation

Problem Statement: Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching ...
173 views

### Count number of ways to achieve a sum [closed]

The Question : Utkarsh being a very talkative child, was scolded by his teacher multiple times. One day, the teacher became very angry and decided to give him a very rigorous punishment. He ...
50 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. ...
498 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 ...
76 views

### NAddOdd - Topcoder - Single Round Match 714 Round 1 - Division I, Level Two

I am interested in DP problems from the past couple of days and am trying to solve various problems on topcoder. To be very frank could not even solve a single one till now. I went through https://...
308 views

### Path Finding using Dynamic Programming

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I ...
435 views

### Find the length of the longest Common Subsequence

I have a DP based implementation for the Longest Common Subsequence(LCS) problem to find the length of the LCS. I wanted to know if there is room for improvement in terms of efficiency(space/time). ...
511 views

### Recursive function and memorization to find minimum operations to transform n to 1

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution. ...
1k views

### Maximum path sum in a triangle with prime number check

I was given this algorithm task: You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below; You will start from the top and move ...
772 views

### LeetCode Minimum Path Sum algorithm

I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time ...
155 views

### Using dynamic to avoid code duplication when wrapping an API

I am dealing with 3 different types of cameras from the same manufacturer and want to write a wrapper for their API. The API structure is like this: Camera1 and Camera2 use the class ...
602 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 ...
1k views

### Longest common subsequence length and backtracking the string

Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...
510 views

### Find the longest rectilinear path in a matrix with descending entries

Problem (Skiing): Each number represents the elevation of that area of the mountain. From each area (i.e. box) in the grid, you can go north, south, east, west - but only if the elevation ...
1k views

### Length of longest palindrome subsequence

I had an interview, where I was asked to solve to this question: Given an string str, find the maximum length of palindrome subsequence. Example: >if str = 'abcda': maximum_length = 3 '...
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 ...
959 views

### Find the maximum profit if given an array of daily stock prices and allowed to buy and sell twice

I am wondering about the correctness of this method: We are given a function / algorithm findMaxProfit() that can find the maximum profit when given an array of ...
1k views

### Coin change with Dynamic Programming

I have made an implementation of coin change problem solved with Dynamic Programming. Could you guys help with renaming some method and variables? Here is my implementation - ...
150 views

### Counting increasing subsequences with a “hacker's” Binary Index Tree

This is an $O(n \sqrt n)$ solution to the the following problem: Given a sequence, compute the number of non-empty increasing subsequences The algorithm is to compute ...
135 views

### Find the minimum number of operations to convert 1 into n, and print the sequence of numbers

Here is my solution for the following task: Given an integer n, print the minimum number of operations needed to obtain the number n starting from the number 1, and the sequence of numbers towards the ...
270 views

### Solution to Google Code Jam 2008 round 1C problem B

This is my solution to Google Code Jam 2008 round 1C problem B (Ugly Numbers). I think it's very elegant. However, I wonder if it's too concise. What could I improve here? The problem: Once upon a ...
142 views

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

This is my second attempt to solve this problem, my first attempt is here: UVA 100: "The 3n + 1 problem" This time I tried to take lessons from the failures and mistakes You pointed out in ...
942 views

### Finding the max product of a 2D array

Given a 2D array of unsigned integers and a maximum length n, find a path in that matrix that is not longer than n and which maximizes the product of the elements in the path. The output should ...
396 views

### LeetCode 01: Matrix challenge

Recently, I've solved the "01 Matrix" LeetCode problem and the solution was accepted by the LeetCode OJ: Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. ...
658 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,...
362 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 ...
532 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: <...
85 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 ...
2k views

### Yet another Fibonacci number generator

First attempt at dynamic programming. I want to make this run faster and better. fibonacci.cpp ...
444 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 ...
497 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 ...
204 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 ...
987 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 ...
85 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 ...
169 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 ...
336 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 ...
203 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 ...
571 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 ...
3k 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 ...
83 views

### SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
802 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 (...
350 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. ...
986 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, ...
306 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! ...
724 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 ...
468 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 ...
383 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 ...