DP memoization | C++ | Easy Solution | power modulo
\n# Approach\nSimple DP with power modulo\n\n# Complexity\n- Time complexity:O(n^3)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n^3)\n A
\n# Approach\nSimple DP with power modulo\n\n# Complexity\n- Time complexity:O(n^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n^3)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    #define ll long long\n    int dp[101][101][102];\n    long long mod=1e9+7;\n    \n    ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}\n    \n    int solve(vector<int>& nums,int k,int ind,int kota){\n        int take=0,nottake=0;\n        if(k==0){\n            long long kkk=(int)powermod(2,(nums.size()-kota),mod);\n            return kkk;\n        }\n        if(ind>=nums.size())\n            return 0;\n        \n        if(dp[ind][k][kota]!=-1){\n            return dp[ind][k][kota];\n        }\n        if(nums[ind]<=k){\n            take=solve(nums,k-nums[ind],ind+1,kota+1)%mod;\n        }\n        nottake=solve(nums,k,ind+1,kota)%mod;\n        return dp[ind][k][kota]=(take+nottake)%mod;\n    }\npublic:\n    int sumOfPower(vector<int>& nums, int k) {\n        if(nums.size()==1){\n            if(k==nums[0])\n                return 1;\n            else\n                return 0;\n        }\n        memset(dp,-1,sizeof(dp));\n        return solve(nums,k,0,0);\n    }\n};\n```
['C++']