474. Ones and Zeroes

寻找单一最优解时，往往采用动态规划的方法，这道题也不例外。
那么第一件事，就是寻找递推公式。
可以考虑构建二维动态规划矩阵，其中need_str_count[i][j]表示，在用i个0，j个1时，可以构建的字符串个数。
若一个字符串demo_str可以被构建，且有a个0，b个1
则应满足：
need_str_count[i][j] = need_str_count[i-a][j-b] + demo_str

注意：这题有个小陷阱，给出的strs中有重复的，所以需要预处理并记录个数。
代码如下：

def solve(strs, m, n):
    def cal_sum(this_dict):
        this_result = 0
        for key, value in this_dict.iteritems():
            this_result += value
        return this_result
    need_str_count = [[{} for j in xrange(n+1)] for i in xrange(m+1)]
    is_cops = [[False for j in xrange(n+1)] for i in xrange(m+1)]
    is_cops[0][0] = True
    with_stat = dict()
    for item in strs:
        if item in with_stat:
            with_stat[item][0] += 1
            continue
        zeros = 0
        ones = 0
        for char in item:
            if char == '0':
                zeros += 1
            else:
                ones += 1
        with_stat[item] = [1, zeros, ones]
    for row in xrange(m+1):
        for col in xrange(n+1):
            for key, item in with_stat.iteritems():
                if item[1] <= row and item[2] <= col:
                    if (key not in need_str_count[row-item[1]][col-item[2]] or
                            (item[0] >
                                need_str_count[row-item[1]][col-item[2]][key]
                             )):
                        if (cal_sum(need_str_count[row][col]) <=
                                cal_sum(
                                    need_str_count[row-item[1]][col-item[2]])):
                            if not is_cops[row-item[1]][col-item[2]]:
                                continue
                            import copy
                            tmp = copy.deepcopy(
                                need_str_count[row-item[1]][col-item[2]]
                            )
                            if key not in tmp:
                                tmp[key] = 1
                            else:
                                tmp[key] += 1
                            need_str_count[row][col] = tmp
                            is_cops[row][col] = True
    max_result = 0
    for each_row in need_str_count:
        for each_one in each_row:
            result = 0
            for key, item in each_one.iteritems():
                result += item
            max_result = max(result, max_result)
    return max_result```