leetcode

Solution to some Leetcode problems written in C++

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

0935.cpp (724B)

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