动态规划用于解决最长公共子序列问题和最小编辑距离问题

【

https://leetcode-cn.com/problems/edit-distance/
https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/

文章结构概述

• 最长公共子序列
  • • 定义说明
    • 实例展示
    • Java语言编程实现

  • 最短编辑距离

  • • 定义说明
    • 实例展示
    • Java语言编程实现

最长公共子序列

描述

设 A = a1a2…an，B = b1b2…bn
定义 L[ i , j ] 为 a1a2…ai 与 b1b2…bj 的最长公共子序列的长度

若 A[i] 等于 B[j]，则 L[ i , j ] 等于 L[ i-1 , j-1 ] 加上 1
若 A[i] 不等于 B[j]，则 L[ i , j ] 等于 L[ i-1 , j ] 与 L[ i , j-1 ] 中的最大值

例如：
A = horse，B = ros
当 i 为 2，j 为 2 时，o 等于 o，L[ ho , ro ] 等于 L[ h , r ] 加上 1
当