算法沉淀——动态规划之其它背包问题与卡特兰数（leetcode真题剖析）

算法沉淀——动态规划之其它背包问题与卡特兰数

• 二维费用的背包问题
• • 01.一和零
  • 02.盈利计划
  • 似包非包
  • • 组合总和 Ⅳ
    • 卡特兰数
    • • 不同的二叉搜索树

        二维费用的背包问题

        01.一和零

        题目链接：https://leetcode.cn/problems/ones-and-zeroes/

        给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

        请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

        如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

        示例 1：

        输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
        输出：4
        解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
        其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
        

        示例 2：

        
        （图片来源网络，侵删）

        输入：strs = ["10", "0", "1"], m = 1, n = 1
        输出：2
        解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
        

        提示：

        • 1 public: int findMaxForm(vector int l=strs.size(); vector int a=0,b=0; for(char ch:strs[i-1]) if(ch=='0') a++; else b++; for(int j=m;j=0;j--) for(int k=n;k=0;k--){ dp[i][j][k]=dp[i-1][j][k]; if(j=a&&k=b) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1); } } return dp[l][m][n]; } }; const int MOD=1e9+7; public: int profitableSchemes(int n, int m, vector int l = group.size(); vector dp[i][j][k]=dp[i-1][j][k]; if(j=group[i-1]) dp[i][j][k]+=dp[i-1][j-group[i-1]][max(0,k-profit[i-1])]; dp[i][j][k]%=MOD; } return dp[l][n][m]; } }; public: int combinationSum4(vector vector public: int numTrees(int n) { vector