[数据结构与算法]lc 动态规划[含有一个记忆化搜索]

1 动态规划

从背包问题开始：

• https://zhuanlan.zhihu.com/p/93857890
  区间dp等等：
• https://oi-wiki.org/dp/interval/

最重要的是，能够用dp数组，1到3维度一般，去表示最终结果，对于具体的题目，dp[i][j]表示什么意思，将成为解答的关键

很多动态规划都可以使用带记忆化的搜索去做

2 例题

0410splitArrayMinMax 分割出最小的子数组最大值

1 题目

https://leetcode-cn.com/problems/split-array-largest-sum/

2 解题思路

参考官方解答：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode-solution/

• 1 dp: 首先搞明白动态规划的单元，注意，不仅仅是说增加一个元素，对分割造成了什么影响，而且还要考虑，不通的分割数目，本题目是分割，那么一定是分割数目以及分割对象带来的变化为dp的状态迁移， dp[i][j] means: res of: nums[:i] to be splited in j’s segments, dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}，所以
• 2 二分查找法：这样，判断一个数字能否作为分割m个子数组的方案？应该很好判断，顺序遍历即可
  • 2.1 那么记录该数字为x，最小就是数组里的最大值，最大即为数组和，于是仅仅需要用二分法，从这个范围中找出该数字即可
  • 2.2 具体如何二分？若x过于小了，会导致分割数目太大，然后我们就知道往大处搜索，反之同理
• 3 二分法的标准写法：
  • 3.1 注意用>>代表除2，尤其是考虑负数时候有区别
  • 3.2 注意当往大地方搜，st = mid+1，往小地方则不用，不然可能导致ed漏搜索

        bool lastCheck = false;
        while(st < ed) {
            x = (st + ed) >> 1; // means: floor of (st + ed)
            lastCheck = xIsLarge(x, nums, m);
            if(lastCheck) {
                ed = x; // when ed - st = 1, (st + ed) >> 1 == st
            } else {
                st = x + 1;
            }
        }
        return st;
 

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> preSum = { 0 };
        for(int i = 0; i < n; ++i) {
            preSum.push_back(preSum.back() + nums[i]);
        }
        // // dp[i][j] means: res of: nums[:i] to be splited in j's segments
        // // dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}
        // vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX));
        
        // dp[1][1] = nums[0];
        // for(int i = 1; i <= n; ++i) {
        //     for(int j = 1; j <= min(m, i); ++j) {
        //         if(j == 1) {
        //             dp[i][1] = preSum[i] - preSum[0];
        //             continue;
        //         }
        //         int tmpMaxMin = 0;
        //         for(int k = j - 1; k < i; ++k) {
        //             tmpMaxMin = max(dp[k][j-1], preSum[i] - preSum[k]);
        //             dp[i][j] = min(dp[i][j], tmpMaxMin);
        //         }
        //     }
        // }
        // return dp[n][m];
        
        // binsearch x as the min max res
        int st = *max_element(nums.begin(), nums.end());
        int ed = preSum[n];
        int x = -1;


        bool lastCheck = false;
        while(st < ed) {
            x = (st + ed) >> 1;
            lastCheck = xIsLarge(x, nums, m);
            if(lastCheck) {
                ed = x; // when ed - st = 1, (st + ed) >> 1 == st
            } else {
                st = x + 1;
            }
        }
        
        // at last, st == ed
        return st;
    }

    bool xIsLarge(int x, vector<int>& nums, int m) {
        int cnt = 1;
        int curSum = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(curSum + nums[i] > x)  {
                ++cnt;
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }
        }
        // cout << ">> x/cnt is" << x << "/" << cnt << endl;
        return cnt <= m;
    }
};

0403frogCrossRiver 青蛙过河

1 题目

https://leetcode-cn.com/problems/frog-jump/

2 解题思路

• 1 动态规划：首先明白动态规划最终是指向结果的，于是，定义dp[i][k]，为到达i的最后一跳长度为k，是否能够跳到目的地
  • 1.1 首先有疑问：那k岂不是max(stone) - min(stone)，那k就会非常大，不合理啊？错，因为每一跳长度最多增加1，然而你最多有n-1跳，于是 k <= n-1
  • 1.2 状态转移: dp[i][k] = dp[j][k] || dp[j][k-1] || dp[j][k+1]，j就是i的上一跳，那么我们可以直到，j到i，k=stone[i] - stone[j]
  • 1.3 需要注意到上面的状态转移: 因为是从j跳，必须保证: k <= j+1，因为你从第j个石头开始跳，最远长度就是j+1

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        // jump to i, and last jump dis
        vector<vector<bool>> jump(n , vector<bool>(n, false));
        jump[0][0] = true;

        // the i th jump len <= i
        for(int i = 1; i < n; ++i) {
            if(stones[i] - stones[i - 1] > i) {
                return false;
            }
        }

        // dp, from j jump to i
        bool res = false;
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                int k = stones[i] - stones[j];
                // cout << j << " -> " << i << " 's dis: " << k << endl;
                if(k > j + 1) {
                    continue;
                }
                // cout << jump[j].size() << " / " << k + 1 << " jump[j][k] || jump[j][k-1] || jump[j][k+1] " << jump[j][k] << jump[j][k-1] << jump[j][k+1] << endl;
                jump[i][k] = jump[j][k] || jump[j][k-1] || jump[j][k+1];
                if(i == n - 1 && jump[i][k]) {
                    res = true;
                }
            }
        }
        return res;
    }
};

0488zumaGame 祖玛游戏

1 题目

https://leetcode-cn.com/problems/zuma-game/

2 解题思路

• 1 对于hand中，每次挑选一个去填补到board中，然后消除board中的球，接着用剩下的hand再选择一个，到board里中去消除，dfs去遍历即可
• 2 使用记忆化搜索 memo[board + " " + hand]记录了对应的board和hand的结果，为何" "是必须的？
  • 2.1 考虑以下例子：
  • 2.2 可以知道必须在中间的RR中先插入B，那么假设我们的第一次搜索从第一个字符G，第二个字符是B，开始，那么我们的memo中会有结果(若是不带空格)：memo[RRYGGYYRBRYYGGYRRGGBB]，这样当第一个字符变成B，我们会在memo发现一个失败的方法直接返回结果，导致改题变成没有结果，同时这个例子也解释了为何减枝的条件3需要在两个相同字符之间插入字符，如果带了空格，就能够绝对避免这个问题，因为：
  • memo[RRYGGYYRBRYYGGYRR GGB] 和 memo[RRYGGYYRBRYYGGYRR GGBB]就能够区分开

“RRYGGYYRRYYGGYRR”

“GGBBB”

class Solution {
public:
    int allBallsCnt = -1;
    map<string, int> memo;

    int findMinStep(string board, string hand) {
        // simulate this game
        int res = 0;
        allBallsCnt = hand.size();
        res = bfs(board, hand);
        return res == INT_MAX ? -1 : res;
    }
    int bfs(string board, string hand) {
        // space mustn't be eliminated! it's neutig!
        if(memo.find(board + " " + hand) != memo.end()) {
            return memo[board + " " + hand];
        }

        if(0 == board.size()) {
            return allBallsCnt - hand.size();
        }
        if(0 == hand.size()) {
            return INT_MAX;
        }

        int useRes = INT_MAX;
        string lastTarBallStr = "";
        for(int k = 0; k < hand.size(); ++k) {
            string nextHand = hand.substr(0, k) + hand.substr(k + 1);
            string tarBallStr = hand.substr(k, 1);

            // case1: cut the same ball
            if(tarBallStr == lastTarBallStr) {
                continue;
            }

            // use this char, find put pos
            for(int i = 0; i <= board.size(); ++i) {
                // case2: only insert at the start of str with same chars
                if(i > 0 && board[i - 1] == hand[k]) {
                    continue;
                }

                // case3: only put when cur is equal current || when cur is not equal to two continuous same chars
                if(i < board.size() && board[i] == hand[k] || \
                i > 0 && board[i] == board[i-1] && hand[k] != board[i-1]) {
                    string tmpBoard1 = board;
                    tmpBoard1.insert(i, tarBallStr);
                    // reduce repeat balls
                    reduceRepeat(tmpBoard1);

                    // put to tarBall left and right
                    int lRes = bfs(tmpBoard1, nextHand);

                    useRes = min(lRes, useRes);
                }
            }
            
            lastTarBallStr = tarBallStr;
        }
        memo[board + " " + hand] = useRes;
        return useRes;
    }

    inline void reduceRepeat(string& board) {
        int idx = 0;
        // cout << "reducing " << board << endl;
        while(board.length() > 0 && idx < board.length()) {
            int st = idx, cur = st;
            char head = board[st];
            while(++cur < board.length() && board[cur] == head) {
            }
            if(cur - st >= 3) {
                board.erase(st, cur - st);
                idx = 0;
            } else {
                idx = cur;
            }
        }
        // cout << "after redu " << board << endl;
    }

};

0552checkRecord 学生出勤记录

1 题目

https://leetcode-cn.com/problems/student-attendance-record-ii/

2 解题思路

• 1 初步思路 dp[i][j]作为直到i天，以j为出勤记录的所有记录数，但是会发现无法处理连续的L的情况
• 2 更改，采用官方题解思路： dp[i][j]为以连续j个l为结尾的记录数，首先只考虑PL，但是此方法不行，因为，A可以隔断两个L，所以，如果先算出所有PL的方法，然后将A插入，那么结果一定会比用A去隔断两个L少。
• 3 官方接单： dp[i][j][k]是含有j个A的k个L为结尾的记录数

class Solution {
public:

    int bigInt = 1000000007;
    int checkRecord(int n) {
        if(n <= 2) {
            return n == 1 ? 3 : 8;
        }
        
        // we can use A to interrupt the LLL, so we calculate A after only PL
        // // n's day without 'A'
        // vector<vector<long long>> dp(n + 1, vector<long long>(3, 0));
        
        // // dp[i][j], j means end with n's L
        // dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0;


        // for(int i = 2; i <= n; ++i) {
        //     // end with p
        //     dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            
        //     // ent with l
        //     dp[i][1] = (dp[i - 1][0]) % bigInt;

        //     // end with ll
        //     dp[i][2] = dp[i - 1][1] % bigInt;
        //     cout << i << " th: P/L: " << dp[i][1] << " " << dp[i][0] << endl;
        // }

        // // when there is a A:
        // long long res = 0;
        // res += ((dp[n][0] + dp[n][1]) % bigInt + dp[n][2]) % bigInt;
        // res += (((dp[n-1][0] + dp[n-1][1]) % bigInt + dp[n-1][2]) % bigInt * n) % bigInt;
       

        // n's day without 'A'
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(2, vector<long long>(3, 0)));
        
        // dp[i][j], j means end with n's L
        dp[0][0][0] = 1;

        for(int i = 1; i <= n; ++i) {
            // end with p
            for(int j = 0; j < 2; ++j) {
                for(int k = 0; k <= 2; ++k) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % bigInt;
                }
            }

            // end with a
            for(int k = 0; k <= 2; ++k) {
                dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % bigInt;
            }
            
            // ent with l
            for(int j = 0; j < 2; ++j) {
                for(int k = 1; k <= 2; ++k) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k-1]) % bigInt;
                }
            }
        }

        int res = 0;

        for(int j = 0; j < 2; ++j) {
            for(int k = 0; k < 3; ++k) {
                res = (res + dp[n][j][k]) % bigInt;
            }
        }


        return res;
    }
};

0600countUncontinous1 不含连续1的非负整数

1 题目

https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/

2 解题思路

• 1 解题思路：
  • 1.1 很显然的动态规划，首先考虑问题： 给你一个二进制数字a = 2^n，判断从0到a有多少个数字不含有连续的两个1？动态规划即可：
    • dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
    • dp[len][1] = dp[len - 1][0];
    • 其中dp[len][0]表示长度为len然后以0开始的二进制数字的集合中，含有多少个不连续为1的数字
  • 1.2 有了上述的思考，那么对于1024，32这种数字的解答就很显而易见了，比如32 = 100000，那么答案就是：首先假设最高位为0，然后res += dp[5][0] + dp[5][1]，这是所有： 0xxxx和1xxxx组成的答案，但是32是6位数字，还需要加上32本身即可
  • 1.3 更近一步，对于a = 101010 和 b = 110000 这样的呢？
    • 以每一个1对结果的贡献来思考，从高位到低位这样去思考：
    • 首先拿a来说，我们看最高位，和32一样的解法，接下来我们找到下一个1，那么就是变成，找以前缀为10，后缀为 0xxx 的有多少种，那么动态规划直接找出来就行，那么为什么不是1xxx，因为1xxx加上前缀10可能就大于a了，就超出了范围，那么我们接着找到下一个1，也就是前缀为1010，找0x有多少种，然后最后找不到1，看看a本身是否合理加上即可
    • 对于b，首先第一个1对最终结果的贡献都是和32一样的，那么第二个1呢？很显然，遇到了连续的第二个1，意味着后面的1对答案都不会有贡献，因为以11为前缀的都是不合法的，所以仅仅需要考虑，将第二个连续的1变成0，以10为前缀，xxxx有多少中方案，很简单，就是 dp[4][0] + dp[4][1]

class Solution {
public:
    int findIntegers(int n) {
        int tmp = n;
        int bit = -1;
        vector<int> bits = {};

        while(tmp > 0) {
            bits.push_back(tmp & 1);
            tmp = tmp >> 1;
        }

        int k = bits.size();
        vector<vector<int>> dp(k, vector<int>(2, 0));

        if(k <= 1) {
            return 2;
        }

        dp[0][0] = 1; // mainly for the last bit is 1
        dp[0][1] = 0;

        dp[1][0] = 1;
        dp[1][1] = 1;

        for(int len = 2; len <= k - 1; ++len){
            dp[len][0] = dp[len - 1][1] + dp[len - 1][0];
            dp[len][1] = dp[len - 1][0];
            // cout << "dp " << len << "/0,1 = " << dp[len][0] << "," << dp[len][1] << endl;
        }

        int lastOneBitIdx = k - 1;

        // assume the biggest bit starts with 0
        int res = dp[lastOneBitIdx][0] + dp[lastOneBitIdx][1];
        // cout << "assume biggest bit = 0's res : " << res << endl;

        bool mySelfOk = true;
        while(lastOneBitIdx > 0) {
            int nextOneBitIdx = lastOneBitIdx - 1;
            cout << ">> last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
            cout << "bits[next] " << bits[nextOneBitIdx] << endl;

            // find next one bit
            while(bits[nextOneBitIdx] != 1) {
                cout << "not 1 bit: " << nextOneBitIdx << endl;
                -- nextOneBitIdx;
                if(nextOneBitIdx == -1) {
                    return res + mySelfOk;
                }
            }

            cout << "last/next: " << lastOneBitIdx << "/" << nextOneBitIdx << endl;
            if(lastOneBitIdx - nextOneBitIdx < 2) {
                // view the bits[nextOneBitIdx] as 0
                res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
                mySelfOk = false;
 
                // cout << "+ dp " << nextOneBitIdx << "," << 0 << " break!!!" << endl;
                break;
            } else {
                // view the bits[nextOneBitIdx] as 0
                res += dp[nextOneBitIdx][0] + dp[nextOneBitIdx][1];
                lastOneBitIdx = nextOneBitIdx;
                // cout << "+ dp " << nextOneBitIdx << "," << 0 << endl;
                // cout << "lastOneBitIdx is " << lastOneBitIdx << endl;
                // cout << "curRes = " << res;

            }
        }

        cout << "me ok: " << mySelfOk << endl;

        return res + mySelfOk;
    }
};