LeetCode 474 Ones and Zeroes

Tag: LeetCode 动态规划 Posted on 2020-06-07 11:15:14 Edited on 2021-03-18 17:13:48 Views: 82

https://leetcode.com/problems/ones-and-zeroes/

状态:由剩余未选择过的字符串个数,剩余未用的 0 的个数以及剩余未用的 1 的个数决定,因此 dp 数组是一个三维数组。

选择:每次首先判断能否构造出当前字符串,选择值大的那个。

代码:

int[][][] dp = new int[m+1][n+1][size+1];
for(int i=0;i<=m;i++) {
    for(int j=0;j<=n;j++) {
        for(int k=1;k<=size;k++) {
            if(strings[k].zero <= i && strings[k].one <= j) {
                dp[i][j][k] = dp[i-strings[k].zero][j-strings[k].one][k-1]+1;
            }
            dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j][k-1]);
        }
    }
}
return dp[m][n][size];

未经允许,禁止转载,本文源站链接:https://iamazing.cn/