For example, we have {2,2,-1}, when k = 0, return -1. when k = 3, return 3. This is even tricky because we have negative numbers and an additional variable k. k can be any value, negative, don...

I am working with the R programming language. Suppose there are 100 people - each person is denoted with an ID from 1:100. Each person can be friends with other people. The dataset can be represent...

Consider below inputs for typical Knapsack problem. V = [10,8,12] W = [2,3,7] i = 1,2,3 C = 10 I tried recursion with memoization to solve this sample but found no overlapping sub problem. Sig...

Here is my requirement, when I click the Add button, dynamically new cards with three TextFields should be generated, and how to assign each TextField with dynamically created TextEditingControlle...

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms? How are the two terms different? I do not understand the difference between them. Please take a sim...

In my actual DAG, I need to first get a list of IDs and then for each ID run a set of tasks. I have used Dynamic Task Mapping to pass a list to a single task or operator to have it process the list...

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

We have a bit array like below {1 0 1 0 0 1 0 1} Number of bits in above array is 8 If we take range from [1,5] then number of bits in [1,5] range is [0 1 0 0 1]. If we flip this range then aft...

What I have learnt is that dynamic programming (DP) is of two kinds: top-down and bottom-up. In top-down, you use recursion along with memoization. In bottom-up, you just fill an array (a table). ...

In an interview I was asked this question: given some array of positive integers s, find the length of the longest subarray such that the sum of all its values is less than or equal to some positiv...

There's an array A containing (positive and negative) integers. Find a (contiguous) subarray whose elements' absolute sum is minimal, e.g.: A = [2, -4, 6, -3, 9] |(−4) + 6 + (−3)| = 1 <- minima...

Given a string S of length N, return a string that is the result of replacing each '?' in the string S with an 'a' or a 'b' character and does not contain three identical consecutive letters (in ot...

I want to know how to find the LIS of an array using Top Down Dynamic Programming. Does there exist one such solution? Can you give me the pseudocode for finding the LIS of an array using Top Down ...

In every single example I've found for a 1/0 Knapsack problem using dynamic programming where the items have weights(costs) and profits, it never explicitly says to sort the items list, but in all ...

I'm having some trouble getting the correct solution for the following problem: Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n sta...

The problem I am talking about is the one below : Consider a rat placed at (0, 0) in a square matrix m[ ][ ] of order n and has to reach the destination at (n-1, n-1). The task is to find a sorted...

I have a question which asks us to reduce the string as follows. The input is a string having only A, B or C. Output must be length of the reduced string The string can be reduced by the fol...

here is another dynamic programming question (Vazirani ch6) Consider the following 3-PARTITION problem. Given integers a1...an, we want to determine whether it is possible to partition of {1...n} ...

I'm trying to understand the Wagner–Fischer algorithm for finding distance between to strings. I'm looking through a pseudocode of it in the following link: http://en.wikipedia.org/wiki/Wagner%E2%8...

Problem: I am struggling to understand/visualize the Dynamic Programming approach for "A type of balanced 0-1 matrix in "Dynamic Programming - Wikipedia Article." Wikipedia Link: https://en.wikipe...

If we have n steps and we can go up 1 or 2 steps at a time, there is a Fibonacci relation between the number of steps and the ways to climb them. IF and ONLY if we do not count 2+1 and 1+2 as diffe...

The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems. The top-do...

I came across an interview questions and despite the fact I've been trying to solve it on my own I think I need some help. I've got an array of integer numbers (positive and negative) representing ...

This problem is an addition to the familiar stack question(https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/) where we have to return the minimum number of additions to make the ...

I recently discovered Codility and I'm going on with the demo training. I wrote this solution to the Genomic Range Query problem, it works fine, solution is provided with dynamic programming, but i...