class Solution { public: int numOfWays(vector<int>& nums) { int m = nums.size(); table.resize( m + 1); for(int i = 0; i < m + 1; ++i){ table[i] = vector<long long> (i+1, 1); for(int j = 1; j < i ; ++j) table[i][j] = (table[i-1][j-1] + table[i-1][j])%mod; } return (dfs(nums) - 1) % mod; } private: vector<vector<long long>> table; long long mod = 1e9+7; long long dfs(vector<int>& nums){ int m = nums.size(); if( m < 3) return 1; vector<int> leftNodes, rightNodes; for(int i = 1; i < m ; i++){ if( nums[i] < nums[0]) leftNodes.push_back(nums[i]); else rightNodes.push_back(nums[i]); } long long leftWays = dfs(leftNodes) % mod; long long rightWays = dfs(rightNodes) % mod; return (((leftWays * rightWays) % mod) * table[m-1][leftNodes.size()])%mod; } };
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