leetcode每日一题：3181.执行操作可获得的最大总奖励 II

 题干：

读本文前，请先弄懂上一篇中的内容，因为这是对上一篇内容的优化：

3180.执行操作可获得的最大总奖励I

明白上篇的，访问值的影响、复制、上下行之间的关系和算法后可继续看：

上一篇中，我们用二维数组，第二维表示了状态空间。

但是，在今日的题目中，提交不行，因为占用的空间太太太大了

关键：我们可以把每行用一个二进制数表示

转化为二进制后：
第一行：1000 0000 0000 0000 00
第二行：1100 0000 0000 0000 00
第三行：1101 1000 0000 0000 00
第四行：1101 1101 0000 0000 00
第五行：1101 1111 0111 0000 00
第六行：1101 1111 0111 1111 10
这样我们节省了太多的空间了
不过像这样 0 -> 17 左小右大实际不好操作，因为上述的二进制值右边才是小的数

左右调转一个方向，这样，小的数和小的位置对应上了
即：
00 0000 0000 0000 0001
00 0000 0000 0000 0011
00 0000 0000 0001 1011
00 0000 0000 1011 1011
00 0000 1110  1111  1011
01 1111  1110  1111  1011

接下来要做的就是把行复制/更新那些操作，在二进制数上实现
原来代码：

class Solution(object):
    def maxTotalReward(self, rewardValues):
        #先从小到大排序，易于计算
        rewardValues.sort()
        n = len(rewardValues) + 1
        m = rewardValues[n-2] * 2 + 1 
        #f用于记录每次访问元素后，状态空间各值可到达情况，初始全为False
        f =  [[False for _ in range(m)] for _ in range(n)]
        
        #第一行单独处理
        f[0][0] = True
        #从第二行开始
        for i in range(1,n):
            #第i行时对应第i-1元素
            v = rewardValues[i-1]
            for j in range(0,m):
                #复制下来
                f[i][j] = f[i-1][j]
                #v~v*2-1特殊处理
                if j>=v and j<2*v:
                    f[i][j] = f[i][j] or f[i-1][j-v]#取/不取 有一个可以达到就行
        
        for j in range(m-1,-1,-1):
            if f[n-1][j] :
                return j

原来用于记录的二维数组：f [ n ] [ m ]    ---->   f [ n ]
原来for循环中复制上一行：f [ i ][ j ] = f [ i -1 ][ j ]  ---->  f [ i+1 ] = f [ i ] 直接整行复制
v~v *2 -1特殊处理：这是重点和难点

拿表中5、6行举例吧 ，6行时访问的是9
5行：00 0000 1110  1111  1011
6行：01 1111  1110  1111  1011
怎么由这个第5行和数字9得到第6行呢？
先完整复制下来得到： 00 0000 111 0  1111  1011   (蓝色这部分是不会被影响的) (红色是特殊处理的v ~ v * 2 -1 )
红1的结果 = 红1 | 蓝1 = 1 | 1= 1   (红蓝1指的是红蓝色部分从右往左数第1位)
红2的结果 = 红2 | 蓝2 = 1 | 1= 1
...... 
最终有：第6行= 01 1111 1110 1111 1011

如图所示：


重点是蓝色那里
比如第5行 = line5  当前访问值为9
则蓝色部分的操作就是：先保留x的0~8位，再把这9位数向左平移9位
即：
blue = 保留line5的0~8位 ，将0~8位与1求与就保留下来了即： blue = line5 & ( 1 << 9 -1 ) 
blue = blue << 9
然后 line 6 = line5 | blue

抽象出来就是：
上一行-line_last 、当前行-line_now 、当前访问值 v
操作为：
line_now = line_last
blue = line_last & ( 1 << v -1 )
line_now = line_now | (blue  <<  v)

分析完了上代码： 

func maxTotalReward(rewardValues []int) int {
    sort.Ints(rewardValues)
    n := len(rewardValues)
    //特殊处理：如果有maxV与maxV-1两个值，结果直接出
    if n >= 2 && (rewardValues[n-2] == rewardValues[n-1]-1) {
        return rewardValues[n-1] * 2 - 1
    }

    //f用于记录每次访问后的结果
    f := make([]int,n+1)
    //标记0值可以达到
    f[0] = 1
    //遍历rewardValues, i是下标0~n-1
    for i,v := range rewardValues {
        //先把上一行复制下来
        f[i+1] = f[i]
        //特殊处理 v ~ v*2 -1 
            //上次访问的 0 ~ v-1部分 会用于 本次访问的v ~ v*2-1部分
            //用位求与  取出上次访问的 0 ~ v-1部分  比如访问3时要保留0~2,则要与000...00111求与保留0~2 （访问x保留x位）
            last_0_to_vsub1 := f[i] & ((1 << v) - 1)
            f[i+1] = f[i+1] | (last_0_to_vsub1 << v)
    }

    //找到二进制数的长度
    res := bits.Len(uint(f[n]))
    //由于第一位代表0不是1所以减1
    res -= 1
    return res
}

我们可以看到，虽然我们创建了长度为n+1的数组f

但是我们其实每次只会用上一次的结果，再早的丢掉也没关系

如此可以优化空间复杂度，优化代码如下：

func maxTotalReward(rewardValues []int) int {
    sort.Ints(rewardValues)
    n := len(rewardValues)
    //特殊处理：如果有maxV与maxV-1两个值，结果直接出
    if n >= 2 && (rewardValues[n-2] == rewardValues[n-1]-1) {
        return rewardValues[n-1] * 2 - 1
    }

    //f_last是上次结果(上一行)，f_now是当前行
    f_last,f_now := 1,0
    //遍历rewardValues, i是下标0~n-1
    for _,v := range rewardValues {
        //先把上一行复制下来
        f_now = f_last
        //特殊处理 v ~ v*2 -1 
            //上次访问的 0 ~ v-1部分 会用于 本次访问的v ~ v*2-1部分
            //用位求与  取出上次访问的 0 ~ v-1部分  比如访问3时要保留0~2,则要与000...00111求与保留0~2 （访问x保留x位）
            last_0_to_vsub1 := f_last & ((1 << v) - 1)
            f_now = f_now | (last_0_to_vsub1 << v)
        //更新f_last
        f_last = f_now
    }

    //找到二进制数的长度
    res := bits.Len(uint(f_now))
    //由于第一位代表0不是1所以减1
    res -= 1
    return res
}

由于int型的数，可以表示二进制的位数，非常非常有限，稍微大一点的数几百，就会导致溢出。
所以提交运行会报错。
所以考虑使用可以存放更多位的数的数据类型：

参考官方题解，使用big.Int 它能够处理任意大小的整数，适合高精度计算或大数运算的需求
big.Int的左移：X.Lsh(被移数，移动量)
big.Int的位与：X.And(值1，值2)

big.Int的位或：X.Or(值1，值2)
修改后的代码如下：
逻辑和计算完全没变，就是看起来稍微复杂了点，注释解释了对应了上面的哪一步

func maxTotalReward(rewardValues []int) int {
    sort.Ints(rewardValues)
    n := len(rewardValues)
    //特殊处理：如果有maxV与maxV-1两个值，结果直接出
    if n >= 2 && (rewardValues[n-2] == rewardValues[n-1]-1) {
        return rewardValues[n-1] * 2 - 1
    }

    //f_last,f_now分别代表上一行，当前行
    f_last,f_now := big.NewInt(1),big.NewInt(0)
    //遍历rewardValues
    for _,v := range rewardValues {
        //先把上一行复制下来
        f_now = f_last
        //特殊处理 v ~ v*2 -1   last_0_to_vsub1 := f_last & ((1 << v) - 1)
            //1 << v -1
            reserved := big.NewInt(1)     // 1 
            reserved.Lsh(reserved,uint(v))// 1 << v
            reserved.Sub(reserved, big.NewInt(1)) // 1 << v -1
            //f_last & ((1 << v) - 1)
            last_0_to_vsub1 := new(big.Int).And(f_last,reserved)
            //f[i+1] = f[i+1] | (last_0_to_vsub1 << v)
            f_now.Or( f_now, last_0_to_vsub1.Lsh(last_0_to_vsub1, uint(v)) )
        f_last = f_now
    }

    //找到二进制数的长度，并-1
    res := f_now.BitLen() - 1
    //由于第一位代表0不是1所以减1
    return res
}

其实到这里，已经和力扣官方的题解一样了。只是我写的开了一些。