class Solution { public: const int m = 1e9+7; using vvi = vector<vector<int>>; int countWays(int idx, int steps, int arrLen,vvi& dp){ if(idx < 0 || idx >= arrLen) return 0; if(steps == 0) if(idx != 0) return 0; else return 1; if(dp[idx][steps] != -1) return dp[idx][steps]; return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m; } int numWays(int steps, int arrLen) { vvi dp; arrLen = min(steps/2+1,arrLen); dp.resize(arrLen + 1,vector<int>(steps+1, -1)); return countWays(0, steps, arrLen,dp); } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter