LeetCode 474 Ones and Zeroes

LeetCode 动态规划 2020-06-07 11:15:14 2021-03-18 17:13:48 497 次浏览

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];

Links: LeetCode-474-Ones-and-Zeroes