1.8-9号Python猛刷动态规划

今日宽恕:总结不是纠结过去，表达不是“见斑知豹”，还要更多信息整合后去回答。
标题一

3297.统计重新分列后包含另一个字符串|

   示例 1：
  输入：word1 = "abcabc", word2 = "abc"
  输出：10
  解释：
  除了长度为 1 和 2 的全部子字符串都是合法的。
  示例 2：
  输入：word1 = "abcabc", word2 = "aaabc"
  输出：0
  
  解释：
  

• 1 <= word1.length <= 105
  
• 1 <= word2.length <= 104
  
• word1 和 word2 都只包含小写英文字母。
  

   思绪：滑动窗口
遍历s，右移动right， 大于即是 t 字母出现次数的窗口，如果满足，缩小left。
这里只必要调解s和t出现差值，

1. class Solution:
2.     def validSubstringCount(self, s: str, t: str) -> int:
3.        if len(s) < len(t):
4.             return 0
5.        # t字母出现次数与s差
6.        diff = defaultdict(int)
7.        for c in t:
8.             diff[c] +=1
9.        #窗口less 个字母出现次数比t少
10.        less = len(diff)
12.        ans = left = 0
13.        for c in s:
14.             diff[c] -= 1
15.             if diff[c] == 0:
16.                 # c移入窗口，窗口内c出现次数和t一样
17.                 less -= 1
18.             while less == 0:
19.                 if diff[s[left]] == 0:
20.                     # s[left] 移出窗口前，检查次数
21.                     #与t一样，窗口内s[left] 比t少
22.                     less +=1
23.                 diff[s[left]] +=1
24.                 left +=1
25.             ans +=left
26.        return ans

复制代码

因为子串可以重排，只要子串可以涵盖（见 76 题）字符串 t，那么子串就可以通过重排，使得 t 是子串的前缀。以是本题是 76. 最小覆盖子串的求个数版本，做法都是滑动窗口
滑动窗口的内层循环竣事时，右端点固定在 right，左端点在 0,1,2,…,left−1 的全部子串都是合法的，这一共有 left 个，把 left 参加答案。
标题二

62. 不同路径 - 力扣（LeetCode）

   示例 2：

1. <strong>输入：</strong>m = 3, n = 2
2. <strong>输出：</strong>3
3. <strong>解释：</strong>
4. 从左上角开始，总共有 3 条路径可以到达右下角。
5. 1. 向右 -> 向下 -> 向下
6. 2. 向下 -> 向下 -> 向右
7. 3. 向下 -> 向右 -> 向下

复制代码

提示：
  

• 1 <= m, n <= 100
  
• 标题数据保证答案小于即是 2 * 109
  

   思绪一：只能左移或下移，肯定要移动下移m-1，左移n-1
以是有 Cm+n−2m−1​
思绪二：
动态方程：dp[j] = dp[i-1][j] + dp[j-1]
注意，对于第一行 dp[0][j]，大概第一列 dp[0]，由于都是在边界，以是只能为1
  

1. class Solution:
2.     def uniquePaths(self, m: int, n: int) -> int:
3.         cur = [1]*n
4.       
5.         for i in range(1,m):
6.             for j in range(1,n):
7.                 cur[j] += cur[j-1]
8.         return cur[-1]   

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。