Skip to main content

Moving on a Grid / Rock Climbing - Dynamic Programming


Imagine a climber trying to climb on top of a wall.  A wall is constructed out of square blocks of equal size. From each block, the climber can reach three blocks of the row right above: one right on top, one to the right and one to the left ( unless right or left not available because that is end of the wall ).
Find the least costly path from bottom to top where cost is the summation of costs of the blocks used on the path.

Problem Representation: An NxM size grid where each cell has a positive cost C(i,j) associated with it. There exists three possible moves from a cell (i,j) -
  • i+1,j-1     [ diagonally left ]
  • i+1. j       [ above ]
  • i+1.j+1     [ diagonally right ]

Take an array dp[ n ][ m ] that will hold the cost for all cells. Initiate dp[ 0 ][ i ] = C(0,i)  for 0 ≤ i ≤ m. There are three cases to the recurrence: a cell might be in the middle (horizontally), on the leftmost or on the rightmost sides of the grid. Thus, we compute dp[ i ][ j ] as follows- 

After all iteration, result is min( dp[ n ][ i ] ) for all 0 ≤ i ≤ m. To get the actuall path, call a function pathfinder recursively.
Problems to solve: Philosopher's Stone , Tri graphs

Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...
14 comments
Read more

SPOJ 394- ACODE

Problem Statement As from the problem-tag, you can see this is a DP( Dynamic Programming ) problem. Don't know Dynamic Programming? Here are some articles: Codechef , TopCoder . Try to solve a sample problem, for example, Fibonacci Numbers. Let's start cracking the problem. To solve a DP problem, the hardest and important part is to find the relation between previous or next steps and current step . We need to find out how the solution of the current step depends on its previous steps or next steps. Looking at:      2 5 1 1 4        from left to right Step 1: You can only interpret this as 2(B). Decoding- B EAAD  So, DP[1] = 1 Step 2: This can be 5(E) or collaborating with 2, it can be 25(Y). Result is BE AAD + Y AAD . So, DP[2] = 2 Step 3: Can only be interpreted as 1(A). 51 is not valid, as stated in problem. BEA AD + YA AD . DP[3] = 2.  Step 4: Will be interpreted as 1(A). BEAA D + YAA D+... ...
Post a Comment
Read more

Next Smallest Palindrome

Given a number, we have to find the next smallest palindrome which is larger than this number.  The input can be large. We'll store the input in an array. e.g. if input is  1259, array will be, int k[]= {1,2,5,9} To find the next smallest palindrome, we have to generalize the input. There can be three types of input.    All digits are 9. e.g. 999 Input is not a palindrome. e.g 12942 The input itself a palindrome number. e.g. 1221 Algorithm for the first type is easy. Expand the array length by one and put boundary digits as 1 & all other digits will be 0.  Input :    999 Output : 1001   Left half & Right half : Using example, left half of 522665 is, 522 & left half of 52123 is 52 . Right half of 522665 is 665 & right half of 52123 is 23 .   Iteration: We'll compare between left half and right half, starting from middle. For example, two variable i and j will indicate to 2 & 4 respecti...
Post a Comment
Read more