网站开发优秀论文,一页网站,门户网站wordpress哪个比较好,安徽免费网站制作在计算机界中#xff0c;我们总是追求用有限的资源获取最大的收益。
现在#xff0c;假设你分别支配着 m 个 0 和 n 个 1。另外#xff0c;还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 #xff0c;找到能拼出存在于数组中的字符串的最大…在计算机界中我们总是追求用有限的资源获取最大的收益。
现在假设你分别支配着 m 个 0 和 n 个 1。另外还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。 给定字符串数组的长度不会超过 600。 示例 1:
输入: Array {“10”, “0001”, “111001”, “1”, “0”}, m 5, n 3 输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出即 “10”,“0001”,“1”,“0” 。
解题思路
数组含义dp[i][j]给定i个0和j个1能拼出存在于数组中的字符串的最大数量。 状态转移 dp[i][j] Math.max(dp[i-c[0]][j-c[1]]1,dp[i][j]) 拿当前字符串或者不拿
代码
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dpnew int[m1][n1];int[][] helpernew int[strs.length][2];for(int i0;istrs.length;i)for(char c:strs[i].toCharArray())if(c0) helper[i][0];else helper[i][1];for (int[] c:helper)for(int im;ic[0];i--)for (int jn;jc[1];j--)dp[i][j] Math.max(dp[i-c[0]][j-c[1]]1,dp[i][j]);return dp[m][n];}
}
