发表于 | 更新于: | 分类于

关于二进制优化

多重背包问题

  • 在多重背包问题中，将问题简化为01背包问题时，如果采用朴素解法，时间复杂度为O(n),后续中，利用二进制优化，将复杂度降成O(logn)
  • 对于二进制优化，将一个很大的数拆分成若干个数，其中数的规律为1,2,4,8….，最后，不足的数填充即可。例如，数字10，将其拆分成1,2,4,3.四个包,对应的二进制为0000~1111，每个包有拿和不拿两种选择。

二进制优化和二分的关系(快速幂)

牵涉到的题目

372题超级次方

  • 该题中同样用到了优化的思想，刚开始以为二进制优化和二分可以等同，但是并不然，该题的思路是，将一个数不断二分，二分的条件是,如果数为偶数，二分，如果数为奇数，数减一。
  • 对于求解一个大数的幂，该思路可以可以将复杂度从O(n)降为O(logn),其中时间复杂度O(n)对应着朴素解法。
  • 同样是优化，二进制优化是为了方便从0~n任何一个数之间进行选取。而二分(快速幂)则是为了将一个很大的指数迅速拆分成一个很小的数，从而降低乘法的次数。
  • 其次，本题中的另外一思路为，先将一个很大的指数拆分成小于10的数，用的是高中数学，同底数幂运算和幂的乘方运算。

    取模公式

  • (a∗b)%MOD=((a%MOD)∗(b%MOD))%MOD

    二分最关键的一步

  • 找到区间上的二段性
  • 目前遇到的两种类型的二分题目，一种是已知连续区间，找未知的值(475),另一种是在非连续单调递增区间内找已知的值

发表于 | 更新于: | 分类于
  • 心得:对于动态规划的题，最核心的思想就是找状态转移方程。
  • 例题：322,638两道题是硬币问题的典型例题 可以用递推，也可以用递归，但是638由于needs的可能性太多 递推方式首先舍去。递归递推具体区别详见:<<算法入门 经典>> P267
  • 例题：第266场leetcode周赛 第二题 统计字符串中的元音子字符串 由于dp[i]只依赖于dp[i-1],可将dp化成0维

    递归模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    // 1. 首先需要设置状态变量 可以是哈希表 也可以是 一维数组 。目的就是存储递归过程中访问过的状态。方便剪枝
    HashMap<Integer,Integer> map=xxxxx;
    int[] visit=new int[];

    public int quesiton(int[],int amount){
        
    }

    // 2. 写递归函数
    public void dfs(xxx){
        // 剪枝  注意:map可以放list，但是不能放数组。数组可以利用Map.entry<>,详见水壶问题dfs
        
        // hashmap
        if(map.contains(x)) return map.get(x);
        // visit
        if(visit[amount]>=0) return dp[amount];

        // map 设置返回值
        int ans=1>>20;
        for(int x:coins){
            // 条件限制 拿硬币问题举例

            // visit
            if(amount>=x) dp[amount]=Math.min(dp[amount],dfs(xxx))

            // hashmap
            if(amount>=x) ans=Math.min(ans,dfs+1)
        } 

        //hashmap
        return ans
        //visit
        return dp[amount]
    }
    阅读全文 »