菜鸡孙连城

题解

/ 注册

全部文章 / 题解（共7篇）

题解 | #75.编辑距离(一)#

看了题解原来这道题这么简单😱 下面我就要抄题解了 dp[i][j]dp[i][j]dp[i][j]表示为从str1str_1str1的前iii位变化为str2str_2str2的前jjj位需要的次数 str1[i]==str2[j]=>dp[i][j]=dp[i−1][j−1]str1[...

Javascript Node 动态规划

2022-03-25

1 282

题解 | #73.最长回文子串#

遍历每个字符，以该字符为中心，不断向两边扩展，求回文字符串的最大长度注意分为奇偶，比如xyzabbaxyz，b为中心的时候分为b和bb function getLongestPalindrome( A ) { function getLength(begin,end){ whil...

Javascript Node 动态规划

2022-03-25

8 412

题解 | #70.兑换零钱(一)#

一开始没看懂dp方程，举个例子，假如现在我们要求10元所需要的货币，此时面值有[1，2，4，7，18，22] 显然无法用18和22参与兑换，因此有arr[j]<=i这个限定条件 10元可以由9元所需货币数加上1元面值由8元所需货币数加上2元面值由7元所需货币数加上3元面值由6元所...

Javascript Node 动态规划

2022-03-25

2 271

题解 | #71.最长上升子序列(一)#

状态转移方程 dp[i]=Math.max(dp[i],dp[j]+1)dp[i] = Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1) 条件：j<i且arr[j]<arr[i]j<i且arr[j]<arr[i]j<...

Javascript Node 动态规划

2022-03-25

1 342

题解 | #68.矩阵的最小路径和#

很简单的dp，状态转移方程：dp[i][j]=matrix[i][j]+Math.min(dp[i−1][j],dp[i][j−1])dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j],dp[i][j-1])dp[i][j]=matrix[i][j]+Mat...

Javascript Node 动态规划

2022-03-24

0 300

题解 | #66.最长公共子串#

这里的dp含义和上一次不一样了，最长公共子序列的dp[i][j]表示str1的i位置和st2的j位置截止的最大长度，而最长公共字串的dp[i][j]表示str1的i位置和str2的j位置作为最后一个元素所构成的最长公共字串，也就是str1的第i个位置必须作为公共子串的最后一个元素，在dp的过程中用...

Javascript Node 动态规划

2022-03-24

1 404

题解 | #65.最长公共子序列(二)#

这道题我只写出了最长公共子序列的长度，公共子序列实际是什么参考了题解 dp是一个二维数组，行数为s1的长度，列数为s2的长度，首先对与dp[0][]和dp[][0]赋值为0或1，代码的9-15行状态转移方程： s1[pi] == s2[j]------>dp[i][j] = dp[i-1]...

Javascript Node 动态规划

2022-03-24

1 308