leetcode

0 // Top-down DP

1 class Solution {

2 static const int MOD = 1E9 + 7;

3 int dp[501][501];

4

5 public:

6 Solution() { memset(dp, 0xFF, sizeof(dp)); }

7 int numWays(const int steps, const int arrLen, const int crnt = 0) {

8 if (steps == 0) return crnt == 0;

9 if (dp[crnt][steps] != -1) return dp[crnt][steps];

10

11 int res = numWays(steps - 1, arrLen, crnt);

12 if (crnt > 0) res = (res + numWays(steps - 1, arrLen, crnt - 1)) % MOD;

13 if (crnt < arrLen - 1) res = (res + numWays(steps - 1, arrLen, crnt + 1)) % MOD;

14

15 return dp[crnt][steps] = res;

16 }

17 };

18

19 // Space optimized, bottom-up DP

20 class Solution {

21 static const int MOD = 1E9 + 7;

22 static int dp[501], pdp[501];

23

24 public:

25 int numWays(const int steps, int arrLen) {

26 memset(pdp, 0x00, sizeof(pdp));

27 arrLen = min(arrLen, steps), pdp[0] = 1;

28 for (int remain = 1; remain <= steps; remain++) {

29 for (int crnt = arrLen - 1; crnt >= 0; crnt--) {

30 int res = pdp[crnt];

31 if (crnt > 0) res = (res + pdp[crnt - 1]) % MOD;

32 if (crnt < arrLen - 1) res = (res + pdp[crnt + 1]) % MOD;

33 dp[crnt] = res;

34 }

35 swap(dp, pdp);

36 }

37 return pdp[0];

38 }

39 };

40

41 int Solution::dp[501];

42 int Solution::pdp[501];