leetcode

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

0935.cpp (724B)

      1 class Solution {
      2     static const int MOD = 1e9 + 7;
      3 
      4   public:
      5     int knightDialer(int n) const {
      6         static const vector<int> offsets[] = {{4, 6}, {8, 6},    {7, 9}, {4, 8}, {3, 9, 0},
      7                                               {},     {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
      8 
      9         vector<int> pdp(10, 1), dp(10);
     10         for (int i = 1; i < n; i++) {
     11             for (int j = 0; j < 10; j++) {
     12                 int res = 0;
     13                 for (const int prev : offsets[j])
     14                     res = (res + pdp[prev]) % MOD;
     15                 dp[j] = res;
     16             }
     17             swap(dp, pdp);
     18         }
     19         return accumulate(begin(pdp), end(pdp), 0, [&](int a, int acc) { return (acc + a) % MOD; });
     20     }
     21 };