leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1269.cpp (1320B)

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];