动态规划新

发表于 | 更新于: | 分类于 |
  • 心得:对于动态规划的题，最核心的思想就是找状态转移方程。
  • 例题：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]
    }

    递推心得

  • 类似Question5这类题,一共有4种写法。外层循环i的顺序不影响内层循环的顺序（也就是j既可以顺序也可以逆序).其中，有两种写法可以用滚动数组实现(也就是将数组降维).dp[i][j]=dp[i-1][任意]; 因为i层只和i-1层有关系。
  • 但是类似于Question64这类题，只有两种（不包括滚动数组），因为dp[i][j]=dp[i-1][j]+dp[i][j-1];如果内层循环j逆序，则无法计算

    2021年11月19日更新

  • Question397题 DFS，BFS，动态规划心得：
  • 对于这一类起点终点确定的有向无环图的题目，如果用dfs，相当于是从结果逆推得到每一步的最优解。如果用bfs，相当于是从起点往终点推，因为保证每一步都是平等的(因为bfs是从步数低往步数高走)，所以只要一遇到终点1,立马返回结果。
  • 其次，对于bfs和dfs的哈希表来说，功能大致相似，bfs中的哈希表有两个作用，一是用于存储步数，二是用判断该值有没有被访问过，后续只要碰到该值，跳过。dfs中的哈希表只有一个作用，用于存储该步数的最优解(因为是从结果开始逆推，所以哈希表存储的一定是最优解)。后续只要碰到该值，就返回哈希表中存储的值。
  • 最后，这道题的边权为1，所以可以用bfs，但是638大礼包题目中边权不为1，因为每个礼包的价格不一样.

    2021年11月20日更新

  • Question2045题，bfs，边权为一，可以用一个统一的变量distance来进行步数的管理。如果用Deque<Integer> queue和HashMap<Integer,Integer> map，反而行不通。
  • Question638题，bfs，边权不为1，就可以用一个Deque<List<Integer>> queue和HashMap<List<Integer>,Integer>，因为不需要像2045题做步数统一.

    递推+记忆化搜索心得

  1. 397题整数替换和375题猜数字大小Ⅱ 充分利用模板解题
  2. 先遍历到底层，再由栈逐层返回
  3. 2021年12月18日更新: 494题目标和，记忆化递归的新想法。一开始没有想到记忆化递归，是觉得每一个状态都是唯一的，不可能第二次碰到。看了看题解，说一说自己的想法。其实朴素递归相当于是后序遍历一颗二叉树，当画出了这棵二叉树之后，写出二叉树的每个节点，可以发现，该题的二叉树还是存在很多重复状态的(因为是自底向上),那么就可以自己定义一个map的key，key=idx+”_”+sum,这样一构造，就不会出现重复了，例如，都是同一个idx但是sum不同，或者，都是同一个sum，但是idx不同。这可能就是动态规划的阶段。
  • 再看大礼包这题的map的key的定义，可以很容易发现直接定义还有多少东西没买的list的就行，但由于这道题是数组中的每个元素都得遍历一遍，且每个元素都有+-两个状态，相当于是一颗边权为1二叉树，大礼包相当于是一个边权不为1的多叉树.

    375

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    static int[][] cache=new int[][];
    public int dfs(){
        // 遍历到最后一层条件，剪枝返回
        if() return 0;
        if(!cache) return cache;
        int ans=Integer.MAX_VALUE
        for(int i;i;i){
            int ret=Math.max()+i;
            ans=Math.min(ans,ret);
        }
        cache[][]=ans;
        return ans;
    }

多重背包问题心得

  1. 多重背包其实可以拆分成完全背包和01背包问题，朴素的讲，就是如果一个物品如果全部装进背包会超载，那么就相当于一个完全背包问题，如果装不完，那就通过二进制优化将物品拆分成一个一个物品，从而转化为01背包问题。
  2. 对于有11个的物品，将其拆分成1，2，4，4四个pack，疑问是会不会漏掉3个这种情况？其实动态规划的本质是求解所有阶段的所有路线的最优解(可以参考数塔问题).那么多重背包问题的本质就是在每个阶段去决策拿与不拿。
  3. 拆分成了1，2，4，4四个物品之后，第一步，有两种选择，拿与不拿，拿就是1个物品的情况，不拿就是0.第二阶段，有1，2两个物品，有四种情况，全不拿，拿1不拿2，拿2不拿1，全拿。分别对应着0，1，2，3.以此类推，从而将时间复杂度从O(n^3)降低到了O(n^2*logn).

    动态规划中的对于连续的总结

  • 对于这类连续的题，dp[i]基本只与dp[i-1]有关，一次遍历可解

    413题 等差数列的划分

  • 该题目中只是计算连续子数组属于等差数列的个数，因此状态转移方程为dp[i]=(condition)?:dp[i-1]+1:0

    意思即为如果满足状态转移方程的条件，则是以上一个元素结尾的等差数列的个数加一.

    2063题 所有子字符串中的元音

  • 该题目中计算连续子序列中元音的个数，状态转移方程为dp[i]=(conditon)?dp[i-1]+i+1:dp[i-1]
  • 如果是要求计算含有元音的子序列的个数，则状态转移方程为dp[i]=(condition)?i+1:dp[i-1]

    两题分别是连续子数组，连续子序列

    设置状态变量 152题 122题

    152题 乘积最大

  • 设置两个状态变量，一个是0，一个是1，负数最小值，正数最大值

    122题 买股票

  • 设置两个状态变量，一个是0，一个是1，0代表不持股，1代表持股

    动态规划中对于非连续的总结

  • 对于这类非连续的题目，dp[i]需要两层遍历递推，如果是区间dp，则三层递推。

    368题 最大整除子集 Arraylist[] dp

    300题 最长递增子序列 int[] dp

    亟待总结的题目 279题和322题 零钱兑换和完全平方数 (背包问题,有向无环图,有明确的起点和终点)

目前遇到过的动态规划的类型

  1. 背包问题
  2. 区间动态规划
  3. 连续型数组(递推)
  4. 非连续型子序列
  5. 硬币问题(完全平方和)，有向无环图
  6. 设置两个状态变量(选与不选，看是否可以转化为01背包问题，416题)
  7. 每个状态有两个抉择，每个抉择分别对下一个状态或者是之后的状态有影响
  • 对应的方法
  1. 递推
  2. 区间dp，三重for循环
  3. 递推，dp[i]只跟dp[i-1]有关
  4. 递推双重for循环
  5. 递推or记忆化递归,完全背包问题
  6. dp[i][2]:两个状态
  7. 正向dp(正推)，反向dp(反推)

    BFS暴搜问题

  • 如果是大礼包这种有向无环图问题， 因为图的边权不为1(每个大礼包的加各不相同),所以此时的bfs相当于是暴搜
  • 如果是类似于找迷宫出口或者是硬币问题，图的边权为1，一旦找到出口，立即返回，那么bfs的效率非常高

2021/12/21 记忆化递归心得

  • 比较了一下526题优美排列和大礼包和494目标和。都用到了记忆化递归的方法，但是区别很大，其中大礼包这道题的记忆化递归用HashMap<List<Integer>,Integer>存储状态，因为题干中说每个大礼包可用无限次，所以状态的定义很简单，可以只定义一个剩余的需求。优美排列这道题中每个数字只能使用一次，故定义一个状态需要两个变量(一个是数组的位置i，另一个是visited),其中visited在其中的作用相当于保证了每个数字只使用一次。其次，目标和这道题中记忆化递归的状态也使用了两个变量。
  • 大礼包状态变量:List needs,状态对应的价格以及题干要求的money，优美排列状态变量:下标idx，访问状态压缩变量visited(代表之前哪些元素访问过),ans题干要求的方案总数，目标和：下标idx，之前元素的总和sum，题干要求的搭配总数map.value
  • 最后，这三道使用记忆化递归的题都用到了回溯的思想。回顾回溯?

记忆化递归和动态规划的关系

  • 通过576.题，动态规划从矩阵边缘(也就是终点)开始往起点推，也就是逆推，记忆化递归也是逆推。恰好，这道题dp和记忆化递归都是逆推。但是，回顾零钱兑换，动态规划既可以逆推，也可以顺推，记忆化递归只能逆推.

2021/12/31 记忆化递归心得

  • 650题记忆化递归，之后凡是看到dfs的参数有两个在变动，那么就说明一个状态至少需要两个变量来决定，就不能单纯的用HashMap类似于这种只能表达一种参数的变量来存储状态

2022/1/17 正向动态规划横向比较

Acm校赛问题G

  • 抉择1，当前节点不走捷径，对下一个节点产生影响，dp[i+1]=math.min(dp[i]+1,dp[i+1])
  • 抉择2，当前节点走捷径，对捷径对应的节点产生影响，dp[arr[i]]=math.min(dp[i]+1,dp[arr[i]]);

    276周赛5982题

  • 抉择1，跳过，对下一个节点产生影响，dp[i+1]=Math.max(dp[i+1],dp[i])
  • 抉择2，不跳过，对s及之后的节点产生影响，dp[s]=Math.max(dp[s],q[0]+dp[i])

记忆化搜索心得 2022.2.8

  • 记忆化搜索是递归到底层，再回溯。类比dp[i][j]的定义方式，拿Uva437来说，相当于是立方体序号为i,第j条边作为高这个状态到不能继续堆立方体的最大高度。
  • 需要满足某种序的条件下，才能递推求出每种状态的值，LC354中由于矩形本身乱序(也可以说是起点终点没有确定)，所以不能利用递归求出每种状态(也就是矩形的序号)的值.

对于递推的几种遍历方式

  • 正序递推，刷表法，但是刷表和正序递推也没有明确的界限，Uva1025的正序(因为刷表递推本该是已知去确定未知，但是该题中如果用刷表递推是未知确定已知),这里可以联系01背包问题的四种递推方式(正序逆序各两种)以及滚动数组.
  • 倒序递推，填表法。

2022/2/22 动态规划中线性结构上的经典模型

最长上升子序列问题

最长公共子序列问题 (朴素解法容易被卡 通过二分+一维dp降低时间和空间复杂度2022/2/22)

2022/2/23 动态规划中的最优矩阵链相乘问题和最优三角剖分问题

  • 思路都是将一个问题划分为一个最优子结构问题。对于最优矩阵链相乘问题来说，下标范围为i~j的矩阵相乘的最优解依赖于更小区间的子结构的最优解(动态规划的本质).
  • Uva10003题，刚开始想的是将状态定义为d[i][j]:先切i，最后切j。这样定义状态导致后续状态转移困难。其次，最开始认为切三刀的最优解依赖于切两刀的最优解，这样看也能转化为最优子结构问题，但是如果这样做就会产生书上所说的一个问题，没有顺序规范化。即便是像参考代码一样考虑到了顺序规范化，将dp[i][j]定义为i~j的最优解，也会产生很多细节问题(边界处理).