动态规划习题其四【力扣】【算法学习day.26】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.一和零

题目链接：474. 一和零 - 力扣（LeetCode）

题面:

基本分析:将该问题转化为背包问题，则f【k】【i】【j】，当考虑到第k个物品，0的个数不超过i，1的个数不超过j的最大子串数目

代码:

class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;// 预处理每一个字符包含 0 和 1 的数量int[][] cnt = new int[len][2];for (int i = 0; i < len; i++) {String str = strs[i];int zero = 0, one = 0;for (char c : str.toCharArray()) {if (c == '0') {zero++;} else {one++;}}cnt[i] = new int[]{zero, one}; }// 处理只考虑第一件物品的情况int[][][] f = new int[len][m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;}}// 处理考虑其余物品的情况for (int k = 1; k < len; k++) {int zero = cnt[k][0], one = cnt[k][1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {// 不选择第 k 件物品int a = f[k-1][i][j];// 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0;f[k][i][j] = Math.max(a, b);}}}return f[len-1][m][n];}
}