Day 29 分而治之, 状态压缩模版

29: 分而治之

剑指 Offer II 101. 分割等和子集

dp[nums.size() - 1][target]
for (int i = 1; i < nums.size(); i++) {
    for (int j = 1; j <= sum; j++) {
        if (j - nums[i] >= 0) {
            dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; 
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

31: 状态压缩模版

const int maxn = 12;
const int inf  = 100000000;

class Solution {
    int n;
    int mat[maxn][maxn];                                   // (1)
    int f[maxn][maxn][1<<maxn];                            // (2)
public:
    void fillGraphMatrix(vector<vector<int>>& graph) {     // (3)
        memset(mat, 0, sizeof(mat));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < graph[i].size(); ++j) {
                mat[i][ graph[i][j] ] = 1;
            }
        }
    }

    int dfs(int st, int en, int state) {                   // (4)
        if(  !( (1<<st) & state ) ) {                      // (5)
            return inf;
        }
        if(  !( (1<<en) & state ) ) {                      // (6)
            return inf;
        }
        if(st == en) {
            if(state == (1<<st)) {
                return 0;                                  // (7)
            }
        }

        int &ret = f[st][en][state];
        if(ret != -1) {
            return ret;                                    // (8)
        }
        ret = inf;
        for(int i = 0; i < n; ++i) {                       // (9)
            // (st -> ... -> i)  U  (i -> en) 
            if(!mat[i][en]) {                              // (10)
                continue;
            }
            int a = dfs(st, i, state);                     // (11)
            int b = dfs(st, i, state ^ (1<<en));           // (12)
            ret = min( ret, min(a, b) + 1 );               // (13)
        }
        return ret;
    }

    int shortestPathLength(vector<vector<int>>& graph) {
        n = graph.size();
        fillGraphMatrix(graph);
        int ret = 100000000;
        memset(f, -1, sizeof(f));

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                int &ans = f[i][j][(1<<n) - 1];
                ans = dfs(i, j, (1<<n) - 1);              // (14)
                ret = min(ans, ret);
            }
        }
        return ret;
    }
};