fancycarp
fancycarp
全部文章
分类
题解(44)
归档
标签
去牛客网
登录
/
注册
fancycarp的博客
全部文章
(共6篇)
NC92 #最长公共子序列#
第一步,通过动态规划找到最长公共子序列长度,并构建dp数组:dp[i][j]:s1[i]和s2[j]为止的最长公共子序列的长度。dp[0][0] = s1[0] == s2[0]dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]dp[0][i] = s1[0] ...
动态规划
2021-05-11
0
499
NC17 #最长回文子串#
经典的动态规划。dp[i][j]代表着从i开始到j为止的子串是不是回文串, l代表回文串长度。状态转移方程:dp[i][j] = 1, l == 1dp[i][j] = A[i] == A[j], l == 2 or l == 3dp[i][j] = dp[i + 1][j - 1] &&a...
动态规划
2021-05-09
0
631
NC65 #斐波那契数列#
最简单的动态规划了 class Solution { public: int Fibonacci(int n) { if(n == 0 || n == 1) return n; int a = 0, b = 1, c; for(int i = ...
动态规划
2021-05-09
0
338
NC127 #最长公共子串#
经典的动态规划题目。dp[i][j]表示以字符串str1 i位置结尾,以字符串str2 j位置结尾的公共字串的长度。状态转移方程:dp[i][j] = dp[i -1][j - 1] + 1, str1[i] == str2[j]dp[i][j] = 0, str1[i] != str2[j] cl...
动态规划
2021-05-08
0
396
题解 | #子数组的最大累加和问题#
动态规划:dp[i]代表以arr[i]结尾的若干个子数组中的和的最大值。状态转移方程:dp[i] = arr[i], if dp[i -1] < 0dp[i] = dp[i - 1] + arr[i], if dp[i - 1] >= 0然后取dp数组里的最大值就行。 class Sol...
动态规划
2021-05-06
0
331
NC68 #跳台阶#
最简单的动态规划 class Solution { public: int jumpFloor(int number) { int dp[number + 1]; dp[1] = 1; dp[0] = 1; for(int i ...
动态规划
2021-05-06
1
913