算法讲解067【必备】从递归入手二维动态规划-算法讲解067【必备】从递归入手二维动态规划

热门回复：

• 左耳朵东:“没见过就不会系列”[支持][支持][支持] 对于不同的子序列那题，递推公式可以这样理解： 假设 s【:i】 中所有子集的数量是 y，其中 x 个子集和 t【:j+1】 相同。 给 s 添加一个字符 s【i】 后，**子集的数量至少会增加 x 个**，也就是给原来那 x 个子集全都**加上一个尾字符 s【i】**，其余新增的子集尾字符也都是 s【i】，所以： 如果 s【i】 != t【j】，新增加的子集全都不与 t【:j+1】 相同，相同的子集数量还是 x，也就是 dp【i】【j】 = dp【i-1】【j】。 如果 s【i】 == t【j】，新增的那 x 个子集中就有可能还有与 t【:j+1】 相同的，数量是多少呢？ 这就要看 s【:i】 的子集中有多少和 t【:j】 相同的，数量就是 dp【i-1】【j-1】，而且这些子集肯定都与 t【:j+1】 不同，不在与 t【:j+1】 相同的那 x 个子集中。 这 dp【i-1】【j-1】 个子集后面再加一个字符 s【i】 后，就成与 t【:j+1】 相同的子集了。 所以 s【:i+1】 的子集中 和 t【:j+1】 相同的数量是 x + 新增的 dp【i-1】【j-1】 个： dp【i】【j】 = dp【i-1】【j】 + dp【i-1】【j-1】。
• MindExplode:等我三个月我出算法新手村
• 忧桑观观1:龟龟二叉树的题目牛客上直接消失了
• bili_21462243600:第一题最小路径和感觉可以用dj算法来，但是实际又会有几个用例不通过，问题出在哪，求左神指教@左程云
• 弹不好的和弦:左神老师，感觉自己懂怎么从递归改动态规划了，但是大部分的题都想不出来递归的暴力解法。