Category: 动态规划

两枚鸡蛋的鸡蛋掉落:单峰性、决策单调性、差分方程

摘要: 单峰性、二分优化 DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本题是基于各种单调性设计算法的经典例子,也是基于目标函数的单峰性、决策单调性优化 DP 的经典例子。从算法的大框架看,有

决策单调性的简单情况:决策候选集随状态推导递增而目标函数不变

摘要: 决策单调性的简单情况 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 决策候选集与最优决策考虑以下状态转移方程: dp[i] = \min\limits_{1\leq j 在推导状态 $dp

单峰性与二分优化DP:N个鸡蛋掉落问题

摘要: 单峰性、二分优化 DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们知道如果一个序列是呈现出单调性的时候,经常设计基于二分的算法。对于动态规划的状态转移方程中,最优决策候选集合有时会呈

求解差分方程/函数方程优化DP:N个鸡蛋掉落问题

摘要: 可以直接作为差分方程/函数方程求解的状态转移方程 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于某些简单的状态转移方程,可以直接作为差分方程/函数方程求解出来。求通项公式很可能会比直接推

使得乘积最大的整数分拆:基于数学性质对决策空间剪枝

摘要: 动态规划解决数列第 n 项问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings \max\limits_{\substack{2 \leq k \leq x \\ \sum_{i=1}^{k

计数DP:基于初等计数原理与容斥原理设计状态表示

摘要: 带限制的排列数目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较困难的计数问题。统计带有某种限制的排列数目,给定的参数有 $n, l, d$ 三个,其中 $n$ 是物品种类

在DP状态转移的DAG上BFS:从动态规划的角度理解无权图最短路径

摘要: 在 DP 状态转移图上 BFS 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在组合数学中,在很多与数列 $\{a_{n}\}$ 相关的问题:给定初始值 $a_{0}, a_{1},\cd

剪枝优化DP:基于数学性质排除大量无效决策

摘要: 剪枝策略减少最优决策候选集中的无效决策 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在基于动态规划解决最优性问题时,状态转移方程中,一个状态对应着很多决策。常规的方式是把这些决策都遍历一遍

无显式结构的动态规划:数列第n项问题

摘要: 动态规划解决数列第 n 项问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings \{a_{n}\}在组合数学中,在很多与数列 $\{a_{n}\}$ 相关的问题:给定初始值 $a_{0},

高维状态设计:凸连通块的状态表示

摘要: 凸连通块的状态表示 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个高维线性动态规划的问题,主要难点在于对矩阵中的连通块的状态表示,其中阶段占了一个维度,附加信息占了 5 个维度

通过离散化处理状态表示中的稀疏维度

摘要: 状态表示中的附加信息要素非常稀疏时,可以用离散化的方式来处理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于动态规划问题,有时仅仅把阶段要素放到 DP 状态中,不足以执行转移。也就是说

优先级队列优化 DP

摘要: 优先级队列优化 DP、自定义堆的比较规则 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们解决一个在棋盘上可以向下或向右行动的问题。本题的特点是每一步可以在给定范围内跳格子行动

树的最大权独立集:树形DP

摘要: 树形DP解决树上最大权独立集问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于没有自环的图 $D$,$S$ 为 $V(D)$ 的子集,若 $S$ 中任意两点均不相邻,则称 $S$ 为

打家劫舍:不相邻子序列最大和问题

摘要: 不相邻的子序列最大 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中我们解决了最大组数组和的问题,以该问题为基础问题有很多变种,在文章 目标带绝对值的处理:最

调整状态定义的方向:简化实现过程

摘要: 状态定义的方向的影响 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 状态计算的方向:从已知状态计算当前状态;从当前状态更新后续状态 中,我们知道当阶段划分与状态定义完成后,还可以转换

阶段不足以表示可推导的状态:附加信息作为状态维度

摘要: 找到阶段划分后,有时发现需要增加附加信息才能得到可以推导的状态表示 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于一个动态规划的问题。最重要的是找到状态表示和阶段划分,其中阶段划分相对

理解高维状态空间线性DP:已处理部分在状态空间中的轮廓

摘要: 状态计算的方向 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过照相排列问题 (k 个串上的线性 DP),来理解一个动态规划中的一个抽象的概念:已处理部分在高维状态空间中的轮廓。可

状态计算的方向:从已知状态计算当前状态;从当前状态更新后续状态

摘要: 状态计算的方向的影响 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划中,当状态表示和阶段划分给定,状态转移方程可以有两个方向的写法可以选,分别对应不同的考虑方式,一个是考虑从先前阶

带权DAG上的最长路径:拓扑序DP

摘要: 拓扑序DP解决带权DAG上的最长路径问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 DAG上的DP (拓扑序DP):无权 DAG 的最长路径 中我们介绍了 DAG 上的拓扑序 D

不同路径系列问题:计数DP,以初等计数原理划分阶段和子问题

摘要: 状态的各决策间满足加法原理,决策划分的子状态间满足乘法原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 动态规划中的计数类问题,主要强调“不重不漏”。因此如果用动态规划解决的话,子结构的划

状态=阶段+附加信息;排除高维状态空间的冗余维度

摘要: 状态=阶段+附加信息,其中有冗余信息的优化方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 高维空间动态规划仅把 DP 的阶段要素放到 DP 状态中有时不足以找到最优子结构,也就是不足

优化状态表示:降低状态转移的复杂性;LCIS问题

摘要: 优化状态表示 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最长上升子序列(LIS)和最长公共子序列(LCS)是单串和双串场景下的动态规划的状态设计思路。 将这两个合起来,形成最长公

最优决策序列个数

摘要: 动态规划解决优化问题,求最优决策方案数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划的问题中,有时会遇到求某个具体的最优决策序列的问题,在 求具体的最优决策序列 中已经解决。 本

数字三角形与数字矩形:两类最经典的棋盘DP状态设计

摘要: 数字三角形问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过数字三角形和数字矩形这两个简单问题来看一下棋盘 DP 的两类基本设计思路。 在棋盘 DP 的问题中,比较常见的有两种

求具体的最优决策序列

摘要: 动态规划解决优化问题,求具体决策序列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划解决的优化问题中,有时需要给出具体的最优方案。最直接的做法是额外使用一些与 DP 状态大小相同的

树状数组优化DP

摘要: 权值树状数组优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 最长上升子序列LIS 我们通过动态规划解决了最长上升子序列问题,其状态转移方程如下: dp[i] = 1 + \m

股票问题-自动机视角(自动机DP)

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

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

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

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

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

多米诺与托米诺骨牌平铺:矩阵快速幂优化DP

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

目标带绝对值的处理:最大子数组和的绝对值

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

【树形DP】树的直径

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

状态压缩DP

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

博弈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 在文章 多米诺与托米诺骨牌平铺 中,我们用矩阵快速幂优化 DP 的方式解决了一个计数问题

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

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

前缀和优化DP

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

最大子矩阵和

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

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

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

背包问题拾遗

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

局部后效性的处理

摘要: 有后效性:状态之间互相转移,互相影响。无法确定合适的阶段。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 有后效性问题的背景阶段是 DP 的三要素之一,无后效性是 DP 算法有效的三个

环形DP

摘要: 环形结构上的动态规划 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 环形结构上的 DP对于环形结构上的 DP,比较直接的思路是: 通过枚举法,选择一个位置将环断开,变成线性结构后进行线

二次扫描与换根DP

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

树形背包

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

分组背包

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

单调队列优化多重背包

摘要: 单调队列优化DP 应用在多重背包问题上 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 多重背包及其二进制划分优化 中我们了解了多重背包问题,以及使用二进制划分的思想来减少状态个数的做法,

最长公共子序列LCS,最经典的双串线性DP状态设计

摘要: 最长公共子序列,最长公共子串,动态规划解法。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一下只要学动态规划就必然涉及的一题:最长公共子序列。它代表了双串上最经典的一类状态设计思

棋盘DP

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