状压总结

LC464. 单词拆分 II

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, vector<string>> memo;

vector<string> backtracking(string &s, int start, unordered_set<string> set)
{
    if (start == s.size())
        return {""};

    if (memo.count(start))
        return memo[start];

    cout << "                    start = " << start << endl;

    vector<string> ret;

    for (int len = 1; len + start <= s.size(); len++)
    {
        string str = s.substr(start, len);
        if (set.count(str))
        {
            vector<string> next = backtracking(s, start + len, set);
            for (auto &ss : next)
            {
                cout << "   ss =  " << ss << endl;
                if (ss == "")
                    ret.push_back(str);
                else
                    ret.push_back(str + " " + ss);
            }
        }
    }
    memo[start] = ret;
    cout << "  start " << start << " memo[start] " << endl;
    for (int i = 0; i < memo[start].size(); i++)
    {
        cout << memo[start][i] << endl;
    }
    return ret;
}

int main()
{

    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    unordered_set<string>
        set(wordDict.begin(), wordDict.end());
    vector<string> ans = backtracking(s, 0, set);

    cout << endl;
    cout << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << endl;
    }
    system("pause");
    return 0;
}

LC464. 我能赢吗

记忆化搜索+状态压缩

#include <bits/stdc++.h>

using namespace std;
unordered_map<int, bool> memo;
bool dfs(int maxChoosableInteger, int usedNum, int desiredTotal, int currSum, bool flag)
{
    if (!memo[usedNum])
    {
        bool ret = false;
        for (int i = 0; i < maxChoosableInteger; i++)
        {
            if (((usedNum >> i) & 1) == 0)
            { // 若此数没被选择 就继续
                cout << " usedNum " << bitset<12>(usedNum) << " currSum " << currSum
                     << " i " << i << (flag ? " me  " : " you ") << bitset<12>(usedNum | (1 << i)) << endl;
                if (i + 1 + currSum >= desiredTotal || !dfs(maxChoosableInteger, usedNum | (1 << i), desiredTotal, currSum + i + 1, !flag))
                {
                    cout << " win " << endl;
                    ret = true;
                    break;
                }
            }
        }
        cout << " usedNum " << bitset<12>(usedNum) << " ret " << ret << endl;
        memo[usedNum] = ret;
    }
    return memo[usedNum];
}

int main()
{
    int maxChoosableInteger = 10;
    int desiredTotal = 11;
    if (desiredTotal < maxChoosableInteger)
        return true;
    if (maxChoosableInteger * (maxChoosableInteger + 1) < 2 * desiredTotal)
        return false;

    cout << dfs(maxChoosableInteger, 0, desiredTotal, 0, true);
    system("pause");
    return 0;
}

struct ListNode {
    int val;
    ListNode next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode next) : val(x), next(next) {}
};

LC1349

class Solution
{
public:
    int maxStudents(vector<vector<char>> &seats)
    {
        int m = seats.size();
        int n = seats[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(1 << n)); //初始化

        for (int row = 1; row <= m; row++)
        {
            for (int s = 0; s < (1 << n); s++)
            {                    //遍历 2^n 个状态
                bitset<8> bs(s); //记录对应状态的bit位
                bool ok = true;
                for (int j = 0; j < n; j++)
                {
                    if ((bs[j] && seats[row - 1][j] == '#') || (j < n - 1 && bs[j] && bs[j + 1]))
                    { //不能坐在坏椅子上也不能在同一行相邻坐
                        ok = false;
                        break;
                    }
                }
                if (!ok)
                {
                    dp[row][s] = -1; //说明坐在坏椅子上或相邻坐了，该状态舍弃
                    continue;
                }
                for (int last = 0; last < (1 << n); last++)
                {                                //找到一种当前行的可行状态后，遍历上一行的所有状态
                    if (dp[row - 1][last] == -1) //上一行的状态被舍弃了，那就直接下一个状态
                        continue;
                    bitset<8> lbs(last);
                    bool flag = true;
                    for (int j = 0; j < n; j++)
                    {
                        if (lbs[j] && ((j > 0 && bs[j - 1]) || (j < n - 1 && bs[j + 1])))
                        {                 //如果找到的这个上一行状态的j位置坐了人，
                            flag = false; //下一行的j+1位置或j-1位置也坐了人，那么该状态不合法，舍弃
                            break;
                        }
                    }
                    if (flag)
                    {                                                                      // flag为真说明这个last状态的每个位置都合法
                        dp[row][s] = max(dp[row][s], dp[row - 1][last] + (int)bs.count()); //转移方程
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < (1 << n); i++)
        { //在最后一行的所有状态中找出最大的
            if (dp[m][i] > res)
            {
                res = dp[m][i];
            }
        }
        return res;
    }
};

时间复杂度M*2^(2N)

空间复杂度M*2^(N)

华为0824

#include <bits/stdc++.h>

using namespace std;

int main()
{
    // vector<vector<int>> seats = {{1, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}};
    vector<vector<int>> seats = {{1, 0, 0, 0}, {0, 0, 0, 1}};
    int total = 0;
    int m = seats.size();
    int n = seats[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(1 << n)); //初始化

    for (int row = 1; row <= m; row++)
    {
        for (int state = 0; state < (1 << n); state++)
        {                         //遍历 2^n 个状态
            bitset<20> bs(state); //记录对应状态的bit位
            bool ok = true;
            for (int j = 0; j < n; j++)
            {
                if ((seats[row - 1][j] == 1) && (bs[j] == 0) || (j < n - 1 && bs[j] && bs[j + 1])) //状态一定要是1 也不能在同一行相邻坐
                {
                    ok = false;
                    break;
                }
            }
            if (!ok)
            {
                dp[row][state] = -1; //说明该状态不包含原有位置，该状态舍弃
                continue;
            }
            for (int lastState = 0; lastState < (1 << n); lastState++)
            {                                     //找到一种当前行的可行状态后，遍历上一行的所有状态
                if (dp[row - 1][lastState] == -1) //上一行的状态被舍弃了，那就直接下一个状态
                    continue;
                bitset<20> lbs(lastState);
                bool flag = true;
                for (int j = 0; j < n; j++)
                {
                    if (lbs[j] && bs[j])
                    { //如果找到的这个上一行状态的j位置坐了人，，那么该状态不合法，舍弃
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    dp[row][state] = max(dp[row][state], dp[row - 1][lastState] + (int)bs.count()); //转移方程
            }
        }
    }
    int res = 0;
    for (int i = 0; i < (1 << n); i++)
    { //在最后一行的所有状态中找出最大的
        if (dp[m][i] > res)
        {
            res = dp[m][i];
        }
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (seats[i][j] == 1)
                total++;
    cout << res - total;
    system("pause");
    return 0;
}