Created
March 21, 2017 06:51
-
-
Save bashmohandes/ed016a2fddb71d107635e88401ef430b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
public class PyramidSlideDown | |
{ | |
public static int LongestSlideDown(int[][] pyramid) | |
{ | |
var cache = new Dictionary<string, int>(); | |
return LongestSlideDownAt(pyramid, 0, 0, cache); | |
} | |
private static int LongestSlideDownAt(int[][] pyramid, int x, int y, Dictionary<string, int> cache) | |
{ | |
if (x >= pyramid.Length || y >= pyramid[x].Length) | |
{ | |
return 0; | |
} | |
if (x == pyramid.Length - 1) | |
{ | |
return pyramid[x][y]; | |
} | |
string key = $"{x}:{y}"; | |
if (cache.ContainsKey(key)) | |
{ | |
return cache[key]; | |
} | |
int max = int.MinValue; | |
for (int i = 0; i < 2; i++) | |
{ | |
int tmp = LongestSlideDownAt(pyramid, x + 1, y + i, cache); | |
if (tmp > max) | |
{ | |
max = tmp; | |
} | |
} | |
cache[key] = pyramid[x][y] + max; | |
return cache[key]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
ماهو الالجوريزم الذي تم استخدامه؟