https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&&tqId=21275&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int minDistance(string& str1, string& str2)
{
    // word与空串之间的编辑距离为word的长度
    if(str1.empty() || str2.empty())
    {
        return max(str1.size(), str2.size());
    }

    int len1=str1.size();
    int len2=str2.size();
    vector<vector<int>> vv(len1+1, vector<int>(len2+1, 0));

    //初始化距离
    for(int i=0; i<=len1; ++i)
    {
        vv[i][0]=i;
    }
    for(int j=0; j<=len2; ++j)
    {
        vv[0][j]=j;
    }

    for(int i=1; i<=len1; ++i)
    {
        for(int j=1; j<=len2; ++j)
        {
            // 判断word1的第i个字符是否与word2的第j个字符相等
            if(str2[j-1]==str1[i-1])
            {
                //由于字符相同，所以距离不发生变化
                vv[i][j]=1+min(vv[i-1][j], vv[i][j-1]);
                vv[i][j]=min(vv[i][j], vv[i-1][j-1]);
            }
            else
            {
                vv[i][j]=1+min(vv[i-1][j], vv[i][j-1]);
                //由于字符不相同，所以距离+1
                vv[i][j]=min(vv[i][j], 1+vv[i-1][j-1]);
            }
        }
    }
    return vv[len1][len2];
}
int main()
{
    string str1, str2;
    while(cin>>str1>>str2)
    {
        cout<<minDistance(str1, str2)<<endl;
    }
    return 0;
}


https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=49&&tqId=29305&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int row=board.size();
        int col=board[0].size();
        vector<vector<int>> vv(row, vector<int>(col, 0));
        vv[0][0]=board[0][0];

        for(int i=0; i<row; ++i)
        {
            for(int j=0; j<col; ++j)
            {
                if(i==0 && j==0)
                    continue;
                if(i==0)
                {
                    vv[0][j]=vv[0][j-1]+board[i][j];
                }
                else if(j==0)
                {
                    vv[i][0]=vv[i-1][0]+board[i][j];
                }
                else
                {
                    vv[i][j]=max(vv[i-1][j], vv[i][j-1])+board[i][j];
                }    
            }
        }

        return vv[row-1][col-1];
    }
};