Longest Binary Subsequence Less Than or Equal to K LeetCode solution in C++

1
class Solution {
2
 public:
3
  int ans = 0;
4
  int f(int i, int size, int sum, string &s, vector<vector<int>> &dp) {
5
    if (i < 0) {
6
      return 0;
7
    }
8
    if (dp[i][size] != -1) {
9
      return dp[i][size];
10
    }
11
    int no = f(i - 1, size, sum, s, dp);
12
    int yes = 0;
13
    if ((sum - (s[i] - '0') * pow(2, size)) >= 0) {
14
      yes = 1 + f(i - 1, size + 1, (sum - (s[i] - '0') * pow(2, size)), s, dp);
15
    }
16
    return dp[i][size] = max(no, yes);
17
  }
18
  int longestSubsequence(string s, int k) {
19
    int n = s.size();
20
    vector<vector<int>> dp(n, vector<int>(n, -1));
21
    return f(n - 1, 0, k, s, dp);
22
  }
23
};