ToBe-YOU

分类

题解(15)

/ 注册

全部文章（共3篇）

题解 | #最长的括号子串#

1.栈用栈保存最近未匹配括号的下标，将栈初始化为{-1}。只有当前字符s[i]为')'且未匹配括号为'('时，弹出栈顶元素，并更新匹配括号子串的最大长度。否则就将当前括号的下标进栈。 class Solution { public: /** * * @param ...

C++ 动态规划字符串栈

2021-12-26

0 408

题解 | #求路径# 空间优化

经典动态规划的方程为： dp[i][j] = dp[i][j-1] + dp[i-1][j] 因为只要求解总路径数，dp[i][j]只与左边和上边的状态有关，不需要保存中间状态。因而可以只用一个数组来保存。当前需要更新的黄色的dp[j]为：刚更新的dp[j-1] 与旧的dp[j]值之和。 cl...

C++ 动态规划

2021-12-18

0 457

题解 | #编辑距离(二)#

1.经典动态规划解法设s[k]为s[0...k]的子串，那么cost[i][j]为从s1[i]编辑为s2[j]的代价。如果s1[i] == s2[j]，那么cost[i][j] = cost[i-1][j-1]; 否则有三种方法可以完成这一次编辑:：用cost[i-1][j-1]的代价...

C++ 动态规划

2021-12-18

1 552