Title:
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
这题仍可以使用动态规划，问题是，如何得到转移方程。
if a[i] == b[j] then d[i,j] = d[i-1,j-1]
但是不相等的情况下如何计算呢
题目给出了三种可能方式，结果就是根据这三种方式进行
if a[i] != b[j] then min(
a[i-1,j]//相当于删除a[i-1]
a[i,j-1]//相当于插入a的末尾，插入的为b的末尾，这样a，b的末尾相等，所以，要同时减1
a[i-1,j-1]//相当于替换
)
https://blog.csdn.net/zxzxzx0119/article/details/82054807
int minDistance(string word1,string word2){
int m = word1.size();
int n = word2.size();
vector<vector<int> > result(m+,vector<int>(n+));
for (int i = ; i <= m ; i++)
result[i][] = i;
for (int j = ; j <= n ; j++)
result[][j] = j;
for (int i = ; i < m; i++){
for (int j = ; j < n ; j++){
if (word1[i] == word2[j])
result[i+][j+] = result[i][j];
else
result[i+][j+] = min(result[i][j+],min(result[i+][j],result[i][j]) )+;
}
}
return result[m][n];
}
其他相关问题：
（1）
最长公共字串（连续）
string a= "abcdef";
string b = "abdef";
可以使用动态规划来解决，使用一个二维数组，状态d[i,j]表示到a[i]和b[j]的最长公共字串，这样问题就是要找出状态转移方程。
如果a[i] = b[j] 那么，d[i,j] = d[i-1,j-1]+1
如果a[i] != b[j] 那么 ，d[i,j] = 0
最后再遍历一下数组，来找出最大的字串。
优化，首先，遍历找出最大字串这一步可以放到计算过程中。
string LCS(string s1, string s2){
int len1 = s1.length();
int len2 = s2.length();
int maxLength = ;
int index = ;
int table[][];
for (int i = ; i < len1+ ; i++)
table[i][] = ;
for (int i = ; i < len2+ ; i++)
table[][i] = ;
for (int i = ; i <= len1 ; i++){
for (int j = ; j <= len2 ; j++){
if (s1[i-] == s2[j-]){
table[i][j] = table[i-][j-] + ;
}else{
table[i][j] = ;
//table[i][j] = (table[i-1][j] > table[i][j-1]) ? table[i-1][j] : table[i][j-1];
}
if (table[i][j] > maxLength ){
maxLength = table[i][j];
index = i;
}
}
}
return s1.substr(index-maxLength,maxLength);
}
例外，一般的动态规划的计算空间都可以降低。将二维空间降至一维空间。
降维对于j一般是正序和逆序，关键是看，如果在计算过程中j-1会被提前计算，则要以相反的顺序进行。比如上面，状态转移是
table[i][j] = table[i-1][j-1] + 1;
如果j是从0 到 len2进行，那么table[j-1]就会被先计算，可是从状态转移我们知道，应该在计算table[j]时，这一行的table[j-1]仍是上一行的，所以应该倒过来进行。
string LCS_continue(string s1,string s2){
int len1 = s1.size();
int len2 = s2.size();
vector<int> result(len2+);
int longest = ;
int index = ;
for (int i = ; i < len2+; i++)
result[i] = ;
for (int i = ; i < len1; i++){
for (int j = len2- ; j >=; j--){
if (s1[i] == s2[j]){
cout<<i<<" "<<j<<endl;
result[j+] = result[j]+;
}else{
result[j+] = ;
}
if (result[j+] > longest){
longest = result[j+];
index = j+;
}
}
}
return s2.substr(index-longest,longest);
}
（2）公共最长子序列（非连续）
非连续的状态转移也很容易得到。
d[i,j] = d[i-1,j-1]+1 (a[i] == b[j])
d[i,j] = max(d[i-1,j],d[i,j-1]) (a[i] != b[j])
同样，在降维的时候，j仍是要逆序进行。
int LCS_not_continue(string s1,string s2){
int len1 = s1.size();
int len2 = s2.size();
vector<int> result(len2+);
for (int i = ; i < len2+; i++)
result[i] = ;
for (int i = ; i < len1; i++){
for(int j = len2- ; j >= ; j--){
if (s1[i] == s2[j]){
result[j+] = result[j]+;
}else{
result[j+] = max(result[j],result[j+]);
}
}
}
return result[len2];
}
（3）最长上升子序列
对于一个序列如1，-1，2，-3，4，-5，6，-7，其最长第增子序列为1,2,4,6
定义递推关系：
dp[i]: 以a_i 为末尾的最长上升子序列的长度
dp[i] = max(1,dp[j]+1) (j < i && a[j] < a[i])
#include <iostream>
#include <vector>
using namespace std; class Solution{
public:
int LIS(vector<int> nums){
vector<int> v(nums.size()+,);
v[] = ;
int result = INT_MIN;
for (int i = ; i < nums.size(); i++){
for (int j = ; j < i; j++){
if (nums[j] < nums[i])
v[i+] = max(v[i+],v[j+]+);
}
/*for (int j = 0; j < i+1; j++){
if (j-1 >= 0 && nums[j-1] < nums[i])
v[i+1] = max(v[i+1],v[j]+1);
}*/
result = max(result,v[i+]);
}
return result;
}
};
int main(){
int a[] = {,,,,};
int size = sizeof(a)/sizeof(int);
vector<int> nums(a,a+size);
Solution solution;
cout<<solution.LIS(nums);
system("pause");
}