关于leetcode1262的问题

Question

bobo老师，在做leetcode1262号问题时，也想尝试用记忆化搜索来解决，但是没想出来递归的状态转移，后来我用一维dp做了一下，就是维护一个dp[3]的状态，每次根据当前数字+上一次的dp结果和3取余，然后根据余数更新dp[3]中的不同位置，这样返回递推如下：
int myMax(int a, int b){

return a > b ? a : b;

}

int maxSumDivThree(int* nums, int numsSize){
int tmp[3] = {0, 0, 0};
int res[3] = {0, 0, 0};

for(int i = 0; i < numsSize; ++i){
    for(int j = 0; j < 3; ++j){
        if((nums[i] + res[j]) % 3 == 0)
            tmp[0] = myMax(tmp[0], nums[i] + res[j]);
        else if((nums[i] + res[j]) % 3 == 1)
            tmp[1] = myMax(tmp[1], nums[i] + res[j]);
        else if((nums[i] + res[j]) % 3 == 2)
            tmp[2] = myMax(tmp[2], nums[i] + res[j]);
    }
    memcpy(res, tmp, sizeof(int) * 3);
}

return res[0];

}

我想通过这个再反推一下递归方式的记忆化搜索，但是还是没有想出来，望bobo老师指点一下记忆化搜索的思路，我大概想了一下是不是记忆化搜索需要用memo[i][mod]这样的方式来记录记忆化搜索结果？感觉这应该是一个类似0-1背包思路的问题，但是始终没绕出来

Answer 1

liuyubobobo 2020-02-18 15:55:02

大赞！

其实我认为，已经有了如此清晰的 dp 思路，可以不思考记忆化搜索的思路了。因为通常情况下，dp 的思路会比记忆化搜索的效率高。

不过，如果一定要做记忆化搜索，我的代码供参考（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/1262-Greatest-Sum-Divisible-by-Three/cpp-1262/main2.cpp 

简单来说，dp[index][mod] 表示使用 nums[index ... n) 能得到的除以 3 余数为 mod 的最大和。要求的就是 dp[0][0]

状态转移有两个，对于当前的 index， mod：

或者不使用 nums[index]，直接转移到 index + 1, mod；

或者使用 nums [index]，此时，由于使用了 nums[index]，要想凑出余数为 mod，应该求用剩下的数字，凑出余数为 (mod - nums[index] % 3 + 3) % 3 的最大和。（思考一下为什么？看着很唬人，其实很简单：））

两者求最大值。

继续加油！：）

• 提问者 慕哥8233928 #1

  谢谢bbobo老师，最主要的就是这个状态转移没想出来，感觉不如一维dp滚动变化好想，关于状态转移：（mod - nums[index] % 3 + 3) % 3 ，这个我理解了一下，应该是这个意思，对于当前的mod，如果有了num的加入，下一次的mod应该更新为几，应该是如下规律：余数为0加余数为0的数余数是0，余数为0加余数为1的数余数是1，余数为0加余数为2的数余数是2；余数为1加余数为0的数余数是1，余数为1加余数为1的数余数为2，余数为1加余数为2的数余数为0；余数为2加余数为0的数余数为2，余数为2加余数为1的数余数为0，余数为2加余数为2的数余数是1。

Answer 2

提问者 慕哥8233928 2020-02-18 17:09:05

谢谢bbobo老师，最主要的就是这个状态转移没想出来，感觉不如一维dp滚动变化好想，关于状态转移：mod - nums[index] % 3 + 3) % 3 ，这个我理解了一下，应该是这个意思，对于当前的mod，如果有了num的加入，剩余的mod应该更新为几，应该是如下规律：余数为0加余数为0的数余数是0，余数为0加余数为1的数余数是1，余数为0加余数为2的数余数是2；余数为1加余数为0的数余数是1，余数为1加余数为1的数余数为2，余数为1加余数为2的数余数为0；余数为2加余数为0的数余数为2，余数为2加余数为1的数余数为0，余数为2加余数为2的数余数是1，按照这个思路计算在有num的参与下 下一次的mod应该是几。

• liuyubobobo #1

  完全正确：）继续加油！：）