牛客882265878号
牛客882265878号
全部文章
分类
题解(5)
归档
标签
去牛客网
登录
/
注册
牛客882265878号的博客
全部文章
(共2篇)
题解 | #最大正方形#
动态规划:第一,使用二维数组dp,确定其元素含义,此处dp[i][j]表示原二维数组第i行第j列位置元素作为正方形右下角构成的最大正方形边长,即该元素必然为‘1’,若为‘0’则无法构成正方形;第二,建立状态转移方程:若matrix[i][j]为'1'时,需要检查其左、上、左上角在dp数组中的值,要构...
C++
动态规划
2021-09-15
0
213
题解 | #最长公共子串#
动态规划方法:首先使用二维数组dp,确定其元素dp[i][j]的含义(此处指str1的第i个元素和str2的第j个元素为结尾的最长公共子串长度,注意最后一个元素必然是相同的)。然后找到状态转移方程:若新加入元素相同,则在原长度加一,即dp[i][j]=dp[i-1][j-1]+1,否则为0。接着考虑...
C++
动态规划
2021-09-15
0
383