Skip to content

Instantly share code, notes, and snippets.

@tzachz
Created December 18, 2013 17:39
Show Gist options
  • Save tzachz/8026568 to your computer and use it in GitHub Desktop.
Save tzachz/8026568 to your computer and use it in GitHub Desktop.
Spiderman exersize
public class Spiderman {
public int spiderman(int n) {
// we're going to calculate these for each floor, starting from first floor:
int waysToGetToThisFloorByJumpingTwoFloors = 0; // there's no -1 floor, so there's no way to jump two floors and get to first floor
int waysToGetToThisFloorDirectlyFromPreviousFloor = 1; // there's one way to get from 0 to 1
int totalWaysToGetToThisFloor = 0;
for (int floor=1; floor <= n; floor++) {
// total ways = sum of ways ending with a big jump (2 floors) and ways ending with a small jump (1 floor):
totalWaysToGetToThisFloor = waysToGetToThisFloorDirectlyFromPreviousFloor + waysToGetToThisFloorByJumpingTwoFloors;
// now, preparing for next floor (floor+1):
// since there were X ways to get to 'floor' from floor-1,
// and we can jump straight from floor-1 to floor+1,
// there are exactly X ways to get to floor+1 which end with jumping two floors:
waysToGetToThisFloorByJumpingTwoFloors = waysToGetToThisFloorDirectlyFromPreviousFloor;
// since there were, in total, Y ways to get to 'floor',
// and we can jump one floor from floor to floor+1,
// there are Y ways to get to floor+1 which end with jumping one floor:
waysToGetToThisFloorDirectlyFromPreviousFloor = totalWaysToGetToThisFloor;
}
// we get here after the last calculation was made for floor n,
// so totalWaysToGetToThisFloor = total ways to get to floor n, which is what we needed
return totalWaysToGetToThisFloor;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment