Memorization -> Tabulation -> Space Optimization
Memorization\n\nLet $solve(target, i)$ denotes the longest subsequence starting from $i$ that sums to target.\n\nFor the $i^{th}$ element, we have two options:\
# Memorization\n\nLet $solve(target, i)$ denotes the longest subsequence starting from $i$ that sums to target.\n\nFor the $i^{th}$ element, we have two options:\n\n- Use `a[i]` to sum up\n- Ignore `a[i]`\n\nThen, we have $solve(target,i) = \\max\\{solve(target-a[i],i+1), solve(target, i+1)\\}$\n\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int lengthOfLongestSubsequence(vector<int>& a, int target) {\n        dp.resize(target+1, vector<int>(a.size(), -1));\n        int ans = solve(a, target, 0);\n        return ans < 0 ? -1 : ans;\n    }\n\n    int solve(vector<int> &a, int target, int i) {\n        if (target == 0)\n            return 0;\n        if (target < 0 || i == a.size())\n            return INT_MIN;\n\n        if (dp[target][i] != -1)\n            return dp[target][i];\n        // we have two options: pick i-th or not\n        return dp[target][i] = max(\n            1 + solve(a, target - a[i], i+1), \n            solve(a, target, i+1)\n        );\n    }\n};\n```\n\n- Time complexity $O(mn)$\n- Space complexity $O(mn)$\n\n# Tabulation\n\n```cpp\nclass Solution {\npublic:\n    int lengthOfLongestSubsequence(vector<int>& a, int m) {\n        int n = a.size();\n\n        vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MIN));\n        for (int i = 0; i <= n; i++)\n            dp[i][0] = 0;\n        for (int i = n-1; i >= 0; i--) {\n            for (int j = 1; j <= m; j++) {\n                dp[i][j] = dp[i+1][j];\n                if (j >= a[i])\n                    dp[i][j] = max(dp[i][j], 1 + dp[i+1][j-a[i]]);\n            }\n        }\n        return dp[0][m] < 0 ? -1 : dp[0][m];\n    }\n};\n```\n\n# Space optimization\n\nWe need to use smaller $j$ from last row (row $i+1$) to update larger $j$ in current row (row $i$), so we can iterate $j$ from $m$ to $1$\n\n```cpp\nclass Solution {\npublic:\n    int lengthOfLongestSubsequence(vector<int>& a, int m) {\n        int n = a.size();\n\n        vector<int> dp(m+1, INT_MIN);\n        dp[0] = 0;\n\n        for (int i = n-1; i >= 0; i--) {\n            for (int j = m; j >= 1; j--) {\n                if (j >= a[i])\n                    dp[j] = max(dp[j], 1 + dp[j-a[i]]);\n            }\n        }\n        return dp[m] < 0 ? -1 : dp[m];\n    }\n};\n```\n\n- Time complexity $O(nm)$\n- Space complexity $O(m)$\n\n## Cleaner code\n\n```cpp\nclass Solution {\npublic:\n    int lengthOfLongestSubsequence(vector<int>& a, int m) {\n        int n = a.size();\n\n        vector<int> dp(m+1, INT_MIN);\n        dp[0] = 0;\n\n        for (int i = n-1; i >= 0; i--) \n            for (int j = m; j >= a[i]; j--) \n                dp[j] = max(dp[j], 1 + dp[j-a[i]]);\n                \n        return dp[m] < 0 ? -1 : dp[m];\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']