python (65.1k questions)

javascript (44.2k questions)

reactjs (22.7k questions)

java (20.8k questions)

c# (17.4k questions)

html (16.3k questions)

r (13.7k questions)

android (12.9k questions)

Questions - recurrence

Maximum sum path from top left to bottom right in a grid using dynamic programming

So I have a n by n grid with 0 at the top left, grid[0][0] marking the start position, and a 0 at the bottom right, grid[n-1][n-1] marking the end position. The rest of the grid is filled with random ...
test-img

Turkey

python

algorithm

recursion

dynamic-programming

recurrence

Votes: 0

Answers: 1

Latest Answer

The usual max path sum problem has a 2D DP solution, but since we need to track an additional property here, let's try 3D DP. Let us assign numbers to the types of turns: right = 0 diagonal = 1 down...
test-img

Abhinav Mathur

How to Solve Recurrence Relations When Master Theorem is not Applicable

How to mathematically solve the recurrence relations of the following form : T(n)=(2^n)T(n/2) + n^n T(n)=4T(n/2) + n^(2)/logn Is there a generic method to solve these? I realize that master theorem ...
test-img

Dawood Ahmad

algorithm

recursion

math

time-complexity

recurrence

Votes: 0

Answers: 1

Latest Answer

Choosing a path base as n = 2^m we have the recurrence T(2^m) = 2^(2^m)T(2^(m-1)) + (2^m)^(2^m) Calling now TT(.) = T(2^(.)) we follow with TT(m) = 2^(2^m)TT(m-1) + (2^m)^(2^m) This is a linear recurr...
test-img

Cesareo

Why this print statement is executed thhe oppsite order in this recursion?

def isPalindrome(s): """Assumes s is a str Returns True if s is a palindrome; False otherwise. Punctuation marks, blanks, and capitalization are ignored."""...
test-img

HugoWang

python

recursion

recurrence

Votes: 0

Answers: 1

Latest Answer

and does not represent normal day speech as in "apples and oranges" but a boolean expression. If both "sides" of and are true, then the result is true. For or the result is true i...
test-img

Roger Lindsjö

Solving recurrence of divide and conquer using master theorem

Can T(n) = 3T(n/2) + c T(1)=0, solved using master theorem? If yes, I am struggling on understand master theorem now, could someone tell me which case it falls to and why.
test-img

MangHatDa

time-complexity

recurrence

divide-and-conquer

master-theorem

Votes: 0

Answers: 1

Latest Answer

There are different possible approaches for the master theorem. I like the one proposed by Cormen et al. in their book Introduction to Algorithms. If f(n) = O(n^(logb(a-e))) for some constant e>0,...
test-img

Joao Paulo

Posts

Questions

Blogs

Jobs