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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
Stack crashed's user avatar
3 votes
1 answer
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 ...
Y N's user avatar
  • 133
2 votes
1 answer
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 ...
Yoonyou Ryu's user avatar
1 vote
1 answer
110 views

Largest divisible subset optimization

So this is my solution to the following leetcode problem: https://leetcode.com/problems/largest-divisible-subset/description/ How could I optimize this code? I think the run time is \$\mathcal{O}(n^2)...
user3769323's user avatar
7 votes
1 answer
298 views

Dynamic Programming with Project Euler problem 67

I am a beginner with python and programming in general. I started teaching myself about 2 months ago. I've been working my way through Project Euler and a few similar sites to build my chops, and ...
M. Guev's user avatar
  • 73
-3 votes
1 answer
3k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
Zaid Humayun's user avatar
2 votes
1 answer
1k views

Coin Change Problem with Memoization

Purpose Another take on the classic Change-making Problem: Given some set of coins and a value, find the minimum number of coins necessary to add up to this value In my implementation, instead of ...
Jae Bradley's user avatar
  • 1,845
0 votes
1 answer
294 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 ...
JSONParser's user avatar
2 votes
1 answer
2k 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 ...
mycleanlittlescrete's user avatar
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
1 answer
943 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 ...
monster's user avatar
  • 131
2 votes
1 answer
463 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). ...
DntFrgtDSemiCln's user avatar
7 votes
2 answers
700 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. ...
user7875185's user avatar
1 vote
2 answers
81 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://...
BeardAspirant's user avatar
5 votes
3 answers
3k 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 ...
vicosoft'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
0 votes
1 answer
180 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 ...
Gabriel Prá's user avatar
6 votes
1 answer
3k 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, “...
arshovon's user avatar
  • 205
6 votes
1 answer
518 views

Hackerrank - Maximum Disjoint Subtree Product

Problem statement We define an unrooted tree, T, with the following properties: T is a connected graph with nodes ...
Jianmin Chen's user avatar
  • 2,396
6 votes
2 answers
2k 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 'aca' How ...
Harsha's user avatar
  • 1,291
5 votes
1 answer
3k 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 ...
nonopolarity's user avatar
4 votes
1 answer
2k views

Student Attendance Record II

I'm currently working on the Student Attendance Record II problem: Given a positive integer \$n\$, return the number of all possible attendance records with length \$n\$, which will be regarded ...
alecxe's user avatar
  • 17.3k
4 votes
2 answers
814 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 ...
RoyaumeIX's user avatar
  • 157
2 votes
1 answer
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 - ...
yadav_vi's user avatar
  • 496
4 votes
1 answer
168 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 ...
Elliot Gorokhovsky's user avatar
1 vote
1 answer
296 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 ...
Marcus Vinícius Monteiro's user avatar
3 votes
2 answers
1k 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 ...
Elliot Gorokhovsky's user avatar
3 votes
1 answer
2k 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 ...
loremIpsum1771's user avatar
4 votes
1 answer
1k 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. ...
alecxe's user avatar
  • 17.3k
3 votes
2 answers
297 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 ...
gaazkam's user avatar
  • 561
4 votes
1 answer
1k 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, ...
Jianmin Chen's user avatar
  • 2,396
2 votes
2 answers
105 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 ...
Sidharth Samant's user avatar
6 votes
2 answers
816 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: <...
gaazkam's user avatar
  • 561
3 votes
1 answer
246 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 ...
Lin Ma's user avatar
  • 3,453
5 votes
1 answer
1k 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 ...
Lin Ma's user avatar
  • 3,453
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
4 votes
1 answer
1k 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 ...
Lin Ma's user avatar
  • 3,453
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
4 votes
1 answer
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 ...
Sarang Shinde's user avatar
4 votes
1 answer
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, <...
Lin Ma's user avatar
  • 3,453
3 votes
1 answer
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 ...
Emy's user avatar
  • 31
1 vote
2 answers
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 ...
Uma Kanth's user avatar
  • 189
5 votes
1 answer
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 ...
Seeker's user avatar
  • 93
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
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
5 votes
1 answer
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. ...
learningboy's user avatar
9 votes
2 answers
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 ...
Aidenhjj's user avatar
  • 2,373
3 votes
1 answer
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! ...
obendidi's user avatar
8 votes
5 answers
2k 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, ...
Jasdeep Singh Chhabra's user avatar
2 votes
1 answer
571 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 ...
Pavlin's user avatar
  • 163