leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1269.cpp (1320B)

      1 // Top-down DP
      2 class Solution {
      3     static const int MOD = 1E9 + 7;
      4     int dp[501][501];
      5 
      6   public:
      7     Solution() { memset(dp, 0xFF, sizeof(dp)); }
      8     int numWays(const int steps, const int arrLen, const int crnt = 0) {
      9         if (steps == 0) return crnt == 0;
     10         if (dp[crnt][steps] != -1) return dp[crnt][steps];
     11 
     12         int res = numWays(steps - 1, arrLen, crnt);
     13         if (crnt > 0) res = (res + numWays(steps - 1, arrLen, crnt - 1)) % MOD;
     14         if (crnt < arrLen - 1) res = (res + numWays(steps - 1, arrLen, crnt + 1)) % MOD;
     15 
     16         return dp[crnt][steps] = res;
     17     }
     18 };
     19 
     20 // Space optimized, bottom-up DP
     21 class Solution {
     22     static const int MOD = 1E9 + 7;
     23     static int dp[501], pdp[501];
     24 
     25   public:
     26     int numWays(const int steps, int arrLen) {
     27         memset(pdp, 0x00, sizeof(pdp));
     28         arrLen = min(arrLen, steps), pdp[0] = 1;
     29         for (int remain = 1; remain <= steps; remain++) {
     30             for (int crnt = arrLen - 1; crnt >= 0; crnt--) {
     31                 int res = pdp[crnt];
     32                 if (crnt > 0) res = (res + pdp[crnt - 1]) % MOD;
     33                 if (crnt < arrLen - 1) res = (res + pdp[crnt + 1]) % MOD;
     34                 dp[crnt] = res;
     35             }
     36             swap(dp, pdp);
     37         }
     38         return pdp[0];
     39     }
     40 };
     41 
     42 int Solution::dp[501];
     43 int Solution::pdp[501];