Ones and Zeroes

这题是第一次碰到3D动态规划，其实背包的思维以及需要分别拿m和n来建立二维滚动矩阵还有对array里面的字符进行01统计都是很容易想到的，状态方程如下

dp[i][j] = max(dp[i - cur_word.zero_count][j - cur_word.one_count] + 1, dp[i][j])

第一次做卡住的地方还是递推的顺序上，这里必须要想通一点即如果想利用矩阵循环解决这个问题则不能从起点dp[0][0]开始推，因为每一次的循环我们都是对一个词是否能在当前m和n的条件下进行考察，如果从0开始根据状态方程递推则相当于我们会一直无限次的取当前这个词来凑n和m，这不符合这道题一个词只能取一次的要求，所以我们应该从终点也就是最大极限值dp[n][m]开始往下找，因为这里的状态方程已经表明，当前状态只跟之前状态有关，如果自顶向下找则就保证了不会重复多次取一个词，另外通过对循环的下界设定可以免去if判断还可以节省部分时间，可以这么做的原因也是因为我们只需要dp[n][m] 的值，其他的值不需要一定正确，只需要能辅助我们找到dp[n][m]就行了，至于为什么其他的值不一定正确也很容易想到，拿n=3,m=3,array=['10']来看，dp[1][1]的值肯定不是1，所以这里只有dp[n][m]的值才是正确值，其他都是辅助而已，另外Python的标准库数据结构真是慢...

算是一道好题，能了解三维动态规划了

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        tmp = [[x.count('1'), x.count('0')] for x in strs]
        dp = [([0] * (m + 1)) for _ in xrange(n + 1)]

        for word_count in tmp:
            for i in xrange(n, word_count[0] - 1, -1):
                for j in xrange(m, word_count[1] - 1, -1):
                    dp[i][j] = max(dp[i - word_count[0]][j - word_count[1]] + 1, dp[i][j])

        return dp[n][m]

另外给一个最naive的背包DP，空间复杂度O(mnl)，隔了一个月状态真的差了一大截...

class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        l = len(strs)
        tmp = [[x.count('0'), x.count('1')] for x in strs]

        dp = [[[0] * (l + 1) for _ in xrange(m + 1)] for _ in xrange(n + 1)]
        for i in xrange(n + 1):
            for j in xrange(m + 1):
                for k in xrange(1, l + 1):
                    zero = tmp[k - 1][0]
                    one = tmp[k - 1][1]
                    if i >= one and j >= zero:
                        dp[i][j][k] = max(dp[i - one][j - zero][k - 1] + 1, dp[i][j][k - 1])
                    else:
                        dp[i][j][k] = dp[i][j][k - 1]
        return dp[n][m][l]