宫水三叶的刷题日记

分类

题解(28)

/ 注册

全部文章（共3篇）

【宫水三叶の真题精选】一题四解 :「动态规划」&「打表」&「矩阵快速幂」

递推实现动态规划既然转移方程都给出了，直接根据转移方程从头到尾递递推一遍即可。代码： public class Solution { public int Fibonacci(int n) { if (n <= 1) return n; int a ...

Java 动态规划记忆化搜索打表矩阵快速幂

2021-09-06

2 906

【宫水三叶の真题精选】详解动态规划解法

动态规划整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '?'：能够匹配 s 中同一位置的任意字符 '*'：能够匹配任意字符串所以本题关键是分析当出现 '*' 这种字符时，是匹配 0 个字符、还是 1 个字符、还是 2 个字符 ... ...

Java 动态规划线性DP

2021-08-26

4 1021

【宫水三叶の剑指精选】如何利用的「等差」性质降低「正则字符串匹配」算法复杂度（类比完全背包一维优化方式）

动态规划为了方便，使用 ss 代指 str，使用 pp 代指 pattern。整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '.'：能够匹配 s 中同一位置的任意字符 '*'：不能够单独使用 '*'，必须和前一个字符同时搭配使用，数据保证了 ...

Java 剑指Offer 动态规划数学

2021-07-26

36 2182