Leetcode 2311. Longest Binary Subsequence Less Than or Equal to K

[Woodyiiiiiii]

很明显要用到DP。而且题目提到subsequence，这种题型解题思路大概是遍历每个字符，然后从后往前遍历DP。

问题是，如何定义DP的状态。DP的长度肯定是字符串的长度，k的长度太大了肯定不是。

这里定义DP状态：dp[i]表示长度为i的最小之和。

class Solution {
    
    public int longestSubsequence(String s, int k) {

        int dp[] = new int[s.length() + 1];
        int res = 0;
        
        for (char c : s.toCharArray()) {
            
            if (dp[res] * 2 + c - '0' <= k) {
                dp[res + 1] = dp[res] * 2 + c - '0';
                res++;
            }
            
            for (int i = res; i > 0; --i) {
                dp[i] = Math.min(dp[i], dp[i - 1] * 2 + c - '0');    
            }
            
        }
        
        return res;

    }
    
}

另一种做法是贪心法，但不赘述，详情看引用2。

时隔一年重新做了这道题，发现这题就类似于基础题LIS。

当然在这里不像No.300，是不能用二分来优化了。

---

Reference:

• https://leetcode.com/problems/longest-binary-subsequence-less-than-or-equal-to-k/
• https://leetcode.com/problems/longest-binary-subsequence-less-than-or-equal-to-k/discuss/2168227/JavaC%2B%2BPython-One-Pass-O(n)