題目看上去很唬人，但是恰恰是這樣說明該題設計的目的很強，指向dp的01背包，就是為了考01背包設計的。

10年積累的網(wǎng)站設計制作、做網(wǎng)站經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站設計后付款的網(wǎng)站建設流程，更有雞澤免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

像極了中學時代的那種看上去花里胡哨，實質(zhì)上是根據(jù)考點設計出題的題目。（這種題看破出題意圖，往往都很簡單）

為什么說是考察01背包，代碼隨想錄–474.一和零中描述的很清楚，不贅述。

這里直接給出轉(zhuǎn)移方程：
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的上限個數(shù)。

---

既然有了轉(zhuǎn)移方程，那么該如何遍歷呢？
就如同01背包一樣，先循環(huán)k或者先循環(huán)i，j都是可以的，不過在力扣上先循環(huán)k的速度要快些，先循環(huán)i,j速度要比先k慢上不少；
這是先循環(huán)k的性能；

這是先循環(huán)i,j的性能；

k先循環(huán)的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++){//先循環(huán)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;
    }
}

先循環(huán) 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++){//先循環(huán)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背包，那么肯定可以通過滾動數(shù)組的方式將三維優(yōu)化至二維，減少空間開銷（方法核心與01背包空間優(yōu)化一致），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++){//先循環(huán)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;
    }
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：動態(tài)規(guī)劃|474.一和零-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://www.rwnh.cn/article48/eschp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供微信小程序、App開發(fā)、企業(yè)網(wǎng)站制作、網(wǎng)站建設、網(wǎng)站內(nèi)鏈、手機網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)