Tag: 动态规划

2023
算法leetcode

力扣730-统计不同回文子序列

摘要: 不同的回文子序列个数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个比较难的问题，算法的核心是动态规划，根据动态规划阶段的不同选取方式，有普通的区间DP，以及序列自动机两种做法

算法leetcode

力扣940-不同的子序列

摘要: 不同的子序列 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个比较难的问题，算法的核心是动态规划，根据动态规划阶段的不同选取方式，有普通的一维线性DP，以及序列自动机两种做法。

算法图论

Floyd算法

摘要: Floyd算法的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 历届图灵奖得主基本上都有高学历、高学位，绝大多数有博士头衔。这是可以理解的，因为创新型人才需要有很好的文化素养

算法动态规划

股票问题-自动机视角（自动机DP）

摘要: 本文介绍股票系列问题，从自动机的角度理解 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 股票系列问题-高维动态规划 中我们从高维动态规划的角度讨论了股票问题这个系列问题。 如果把操作

数计算数学

牛顿插值的原理与实现

摘要: 牛顿插值的原理与应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在业务场景中，我们经常要找到某个指标与某个因素之间的变化关系，这种变化关系有时可以用函数来表示。 对于这

算法疑难杂症

力扣LCP14-切分数组

摘要: LCP14，分解质因数+哈希表优化DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文看一个分解质因数与动态规划结合的题。直接写出动态规划算法比较简单，但难点在于如何用分解质因数进行优化

2022
算法动态规划

【状态压缩DP】N次操作后的最大分数和

摘要: 一道状态压缩DP的简单题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 状态压缩DP 中我们学习了状态压缩DP的知识，本文我们来看一个相关的经典问题。 题目

算法动态规划

分汤-概率DP与浮点数精度处理结合

摘要: 一道概率 DP 的问题，记忆化搜索 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，前面我们详细学习过概率 DP 这类算法，参考文章 概率DP。【力扣808. 分汤】是力扣上比较少见的

算法动态规划

多米诺与托米诺骨牌平铺

摘要: 动态规划解决计数问题，模下矩阵快速幂优化 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，之前在文章 计数DP 中我们总结了常见的使用动态规划解决计数问题的题目，在文章

算法动态规划

最大子数组和的绝对值

摘要: 本文介绍最大子数组和的一类变种：和最大改为和的绝对值最大 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个

算法leetcode

最大子数组乘积

摘要: 最大子数组乘积，最大子数组和的一个变种问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法

算法leetcode

环形数组上的最大子数组和

摘要: 环形数组上的最大子数组和，有动态规划、前缀和两种解法。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在前一篇文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到

算法疑难杂症

2022力扣秋季赛第4题

摘要: 2022 力扣秋季赛第 4 题，状态复杂到搞人心态的二叉树上的树形 DP 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们来研究一下力扣秋季赛第 4 题，也就是 LCP

算法leetcode

【树形DP】力扣968-监控二叉树

摘要: 力扣 968, 状态比较复杂的树形 DP 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，在文章 【树形DP】树的直径 中，我们学习了树形 DP 的经典题目：树的直径，理

算法动态规划

【树形DP】树的直径

摘要: 力扣 1245, 1522，树的直径，最经典的树形 DP 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，我们继续研究力扣秋季赛的题目。在十一之前参加了力扣秋季赛个人赛，

算法leetcode

【DP难题】力扣1595-连通两组点的最小成本

摘要: 力扣 1575，比较难的图论题，抽象之后是最小边覆盖问题，有状态压缩DP和二分图最大匹配两种解法。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个比较难的图论题，力扣

AI模型强化学习

MDP的动态规划解法-策略迭代和价值迭代

摘要: MDP 假设下的动态规划 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 强化学习环境框架-从一个迷宫环境看MDP的要点 中，我们总结了强化学习的基本概念，以及作为强化学习机制的 MD

AI模型强化学习

价值的定义与计算-贝尔曼方程

摘要: 贝尔曼方程初探 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 强化学习环境框架-从一个迷宫环境看MDP的要点 中，我们总结了强化学习的基本概念，以及作为强化学习机制的 MDP，并且以

算法动态规划

状态压缩DP

摘要: 本文介绍状态压缩 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文参考《算法竞赛进阶指南》 0x5，书中关于状态压缩 DP 的讲解我觉得非常好。之前虽然解决过很多状态压

算法leetcode

力扣2104-子数组的范围和

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 面试好题连载 中，我们提到了适合作为面试题的几个标准大致如下： 对于

算法疑难杂症

LCP04-覆盖

摘要: LCP04，状态压缩DP和二分图匹配两种解法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个比较难的图论题，力扣 LCP04。有状态压缩 DP 和二分图最大权匹配两种解法。之

算法疑难杂症

【组合数学】马拦过河卒

摘要: 很经典并且非常综合的组合数学问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文的第一题，标准的马拦过河卒问题是入门的棋盘 DP 的题目。 如果没有马拦着过河卒，那么 leetcode

算法动态规划

博弈DP

摘要: 本文介绍概率 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 博弈是应用数学的一个分支，表示在多决策主体之间行为具有相互作用时，各主体根据所掌握信息以及对自身能力的认知，做

算法动态规划

期望DP

摘要: 本文介绍期望 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 与概率DP类似(参考文章概率DP)，期望DP不是一种特殊的动态规划类型，而是一种常见的应用场景。类似的还有计数

算法动态规划

概率DP

摘要: 本文介绍概率 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 概率DP并不是一种特殊的动态规划类型，而是一种常见的应用场景。类似的还有计数DP，博弈DP，等等。实际上在解决

数概率

概率与期望计算

摘要: 概率与期望计算若干例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文整理自《算法竞赛进阶指南》0x38，首先介绍概率与期望的基本概念和公式，然后有若干例题。 除了第一题是直接求数学期望

2021
算法动态规划

矩阵快速幂及其动态规划优化中的应用

摘要: 本文介绍矩阵快速幂的算法原理与代码模板，并解决一个例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 多米诺与托米诺骨牌平铺 中，我们用矩阵快速幂优化 DP 的方式解决了一个计数问题

任意门连载合集

【连载】动态规划的优化

摘要: 关于动态规划的优化的文章 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本系列连载是关于动态规划的各种优化方法的。动态规划有很多种优化方式，比较常见的如下图所示 关于动态规划本身，可以参考

任意门连载合集

【连载】动态规划

摘要: 关于动态规划的各个算法点的文章连载 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 编号 网站链接 备注 搬运 1 动态规划概念和基础线性DP - 算法题刷刷

算法leetcode

【DP难题】力扣1411-给Nx3网格图涂色的方案数

摘要: 使用动态规划解决计数问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，最大子数组和这个系列此前连续写了八篇，有些审美疲劳了。今天我们换换脑子，看个使用动态规划解决计数问题的一个例子

算法动态规划

【leetbook】动态规划精讲-目录

摘要: 动态规划系列的 4 本 Leetbook 目录，附链接 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 动态规划精讲1 01 概述 02 动态规划简介 动态规划的背景 解决动态规划问

数概率

【Puzzle】用户一次游戏带来的收入

摘要: 来自朋友的面试的概率题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 写在前面概率面试题连载已经写了几期了，目前的题目主要是《Fifty challenging problems i

算法动态规划

前缀和优化DP

摘要: 本文介绍了动态规划的一种优化方法：前缀和优化 DP。并拆解了力扣第 1871 题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 前缀和优化 DP当 DP 转移方程是如下形式的时候： 计算

算法动态规划

最大子矩阵和

摘要: 最大子矩阵和问题，有两种处理二维情况的方式。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解

算法疑难杂症

力扣LCP34-二叉树染色

摘要: LCP34，树形DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个树形DP的何题，力扣 LCP34，本题是2021力扣杯春季赛团队赛第2题。算法要点如下： 树形DP 二叉

2020
算法动态规划

01背包和完全背包题目汇总

摘要: 转换为 01 背包和完全背包的组合问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 组合数学的问题有时候可以转换为背包问题进而解决，而组合数学研究组合的存在性、计数性、优化性。也就是说背包

算法动态规划

背包问题拾遗

摘要: 背包问题的遗留问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 01背包和完全背包 和 01背包和完全背包题目汇总 中我们分别了解了 01 背包和完全背包的算法原理、代码模板，以及

算法动态规划

后效性处理

$0 有后效性问题的背景阶段是 DP 的三要素之一，无后效性是 DP 算法有效的三个前提之一。参考 动态规划概念和基础线性DP 在一些问题中，抽象出状态维度，并设计出状态表示和状态转移方程后，可能会发现这样的状态设计不满足无后效性，部分状态之间互相转移，互相影响，构成了环形。 对于环形问题，有一种【可拆解的环形问题】，这样的问题是可以拆环后转化成线性结构上的 DP 问题，参考： 环形DP 。 而对

算法动态规划

环形DP

环形结构上的DP 枚举断开位置，求解对应的线性结构上的DP 可拆解的环形DP问题 两次DP 288. 休息时间 213. 打家劫舍 II 1388. 3n 块披萨 复制一倍接在末尾 283. 多边形 变为 2N 长线性数组后用区间DP 289. 环路运输 变为 2N 长线性数组后用单调队列 918. 环形子数组的最大和 算法1: 复制一倍接在末尾 + 前缀和+单调队列 算

算法动态规划

二次扫描与换根DP

摘要: 无根树上的树形DP，二次扫描与换根的处理方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 树形DP 中，我们简要介绍了树形 DP 的思想，以及列举了很多可以解决的问题。 在有的问题

算法动态规划

树形背包

摘要: 树形背包 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一：树形背包。树形背包问题是 树形DP 和 分组背包 的应用。 树形背包问题 10. 有依赖

算法动态规划

分组背包

摘要: 分组背包 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一：分组背包。分组背包是树形背包的基础，同时也是很多树形 DP 中状态转移的基本模型。 分组

算法动态规划

单调队列优化多重背包

01背包和完全背包 多重背包 同余类状态 单调队列 单调队列优化DP $0 6. 多重背包问题 III有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 120<N<=10000<V<=20000 $1 多

算法动态规划

双串线性DP,二维状态表示阶段

子序列匹配 392. 判断子序列 115. 不同的子序列 字符串模糊匹配 72. 编辑距离 712. 两个字符串的最小ASCII删除和 583. 两个字符串的删除操作 44. 通配符匹配 10. 正则表达式匹配 其它 97. 交错字符串 727. 最小窗口子序列 1458. 两个子序列的最大点积 $0 双串线性 DPdp[i][j]: i

算法动态规划

最长公共子序列LCS

最长公共子序列 1143. 最长公共子序列 1035. 不相交的线 最长公共子串 718. 最长重复子数组 求具体的最长公共子序列 1092. 最短公共超序列 $1 最长公共子序列线性DP, 是动态规划中最常见的一个类型. 相比其它类型的DP, 它的状态设计变化非常多. 其中最经典的问题是 LIS, LCS, 它们分别代表了单串和双串的线性 DP 中最经典的状态表示和阶

算法动态规划

棋盘DP

摘要: 棋盘 DP 的题目总结 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在很多时候，我们要在矩阵或者三角形上解决问题。比如给定一个矩阵，求最大的子矩阵和；又比如给定一个三角形，求从第一行走

算法动态规划

单串线性DP-多维状态,在阶段的基础上附加维度

801. 使序列递增的最小交换次数 1187. 使数组严格递增 873. 最长的斐波那契子序列的长度 1027. 最长等差数列 813. 最大平均值和的分组 887. 鸡蛋掉落 256. 粉刷房子 265. 粉刷房子 II 975. 奇偶跳 403. 青蛙过河 1478. 安排邮筒 1230. 抛掷硬币 410. 分割数组的最大值 1473. 给房子涂色 III 446. 等差数列划分 II -

算法动态规划

单串线性DP-一维状态表示阶段

32. 最长有效括号 413. 等差数列划分 91. 解码方法 338. 比特位计数 871. 最低加油次数 978. 最长湍流子数组 656. 金币路径 1024. 视频拼接 639. 解码方法 2 1578. 避免重复字母的最小删除成本 1218. 最长定差子序列 1235. 规划兼职工作 1043. 分隔数组以得到最大和 1416. 恢复数组 1055. 形成字符串的最短路径 368

算法动态规划

最长上升子序列LIS

最长上升子序列 300. 最长上升子序列 DP (单串线性DP基本设计思路) (权值)树状数组优化DP 二分 (LIS 的最优解) 最长上升子序列的基础变形 最长上升子序列个数 673. 最长递增子序列的个数 最长上升子串 (最优解是滑动窗口) 674. 最长连续递增序列 俄罗斯套娃信封 (通过合适的排序转换为 LIS) 二维 354. 俄罗斯套娃信封问题

算法动态规划

有向图上的DP(HMM前向后向计算)

$0 有向图上的 DP (HMM前向后向计算)一些表现形式为有向图 D 上的动态规划的问题，其阶段的推导是在 G 上进行的，如果本阶段在节点 u，u, v 之间没有有向边，则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段，而是作为阶段持有的状态。而阶段另有一个维度表示，并且具有例如长度，时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp