动态规划|474.一和零-创新互联

题目看上去很唬人，但是恰恰是这样说明该题设计的目的很强，指向dp的01背包，就是为了考01背包设计的。

10年积累的网站设计制作、做网站经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有鸡泽免费网站建设让你可以放心的选择与我们合作。

像极了中学时代的那种看上去花里胡哨，实质上是根据考点设计出题的题目。（这种题看破出题意图，往往都很简单）

为什么说是考察01背包，代码随想录–474.一和零中描述的很清楚，不赘述。

这里直接给出转移方程：
f ( k , i , j ) = f ( k − 1 , i , j ) + ( k − 1 , i − [ k ] , j − [ k ] ) f(k,i,j)=f(k-1,i,j)+(k-1,i-[k],j-[k]) f(k,i,j)=f(k−1,i,j)+(k−1,i−[k],j−[k])
其中：k表示候选元素的范围，(i，j)表示0与1的上限个数。

---

既然有了转移方程，那么该如何遍历呢？
就如同01背包一样，先循环k或者先循环i，j都是可以的，不过在力扣上先循环k的速度要快些，先循环i,j速度要比先k慢上不少；
这是先循环k的性能；

这是先循环i,j的性能；

k先循环的Java代码如下：

class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
        int[][][] f = new int[len+1][m+1][n+1];
        
        for(int k = 1; k<= len; k++){//先循环k
            String s = strs[k-1];
            int[] set = getSet(s);
            for(int i = 0; i<= m; i++){for(int j = 0; j<= n; j++){f[k][i][j] = f[k-1][i][j];
                    if(i-set[0] >= 0 && j-set[1] >= 0)
                    f[k][i][j] = Math.max(f[k][i][j], f[k-1][i-set[0]][j-set[1]] + 1);
                }            
            }
        }
        return f[len][m][n];
    }
    int[] getSet(String s){int[] set = new int[2];
        for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
            else set[1]++;
        }
        return set;
    }
}

先循环 i , j i,j i,j的代码如下：

class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
        int[][][] f = new int[len+1][m+1][n+1];
        
        for(int i = 0; i<= m; i++){//先循环i,j
            for(int j = 0; j<= n; j++){for(int k = 1; k<= len; k++){String s = strs[k-1];
                    int[] set = getSet(s);
                    f[k][i][j] = f[k-1][i][j];
                    if(i-set[0] >= 0 && j-set[1] >= 0)
                    f[k][i][j] = Math.max(f[k][i][j], f[k-1][i-set[0]][j-set[1]] + 1);
                }            
            }
        }
        return f[len][m][n];
    }
    int[] getSet(String s){int[] set = new int[2];
        for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
            else set[1]++;
        }
        return set;
    }
}

既然是01背包，那么肯定可以通过滚动数组的方式将三维优化至二维，减少空间开销（方法核心与01背包空间优化一致），Java代码如下：

class Solution {public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;
        int[][] f = new int[m+1][n+1];
        
        for(int k = 1; k<= len; k++){//先循环k
            String s = strs[k-1];
            int[] set = getSet(s);
            for(int i = m; i >= set[0]; i--){//核心点在于i，j的遍历上下界及顺序
                for(int j = n; j >= set[1]; j--){f[i][j] = f[i][j];
                    if(i-set[0] >= 0 && j-set[1] >= 0)
                    f[i][j] = Math.max(f[i][j], f[i-set[0]][j-set[1]] + 1);
                }            
            }
        }
        return f[m][n];
    }
    int[] getSet(String s){int[] set = new int[2];
        for(int i = 0; i< s.length(); i++){if(s.charAt(i)-'0' == 0) set[0]++;
            else set[1]++;
        }
        return set;
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：动态规划|474.一和零-创新互联
URL分享：http://6mz.cn/article/eschp.html