当前状态一定不能从后面的状态推出

解dp题步骤

1.定义dp数组

2.建立状态转移方程

3.确定初始状态

4.验证（循环顺序）

题目描述

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。

给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。

测试样例:"abc",3,"adc",3,5,3,100     返回：8

我的代码：

int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {        // write code here        int dp[310][310] = {
     0};        int tmp = 200;        for(int i = 0; i <= n; i++)            dp[i][0] = i*c1;        for(int i = 0; i <= m; i++)            dp[0][i] = i*c0;        for(int i = 1; i <= n;i++)        {            for(int j = 1; j <= m; j++)            {                tmp = min(dp[i-1][j]+c1,dp[i][j-1]+c0);                if(A[i-1] == B[j-1])                    dp[i][j] = min(tmp,dp[i-1][j-1]);                else                    dp[i][j] = min(tmp,dp[i-1][j-1]+c2);            }        }        return dp[n][m];    }

思路：

1.定义dp数组：dp[i][j],字符串A的前i个字符转换为B的前j个字符的代价。

2.建立状态转移方程

字符串A转换到字符串B,分三种情况：

A的前n-1位转换得到字符串B，这时只需要将A的最后一位删掉即可  dp[i-1][j]+c1

A转换成字符串B的前m-1位，这时只需要添加B的最后一位即可　　dp[i][j-1]+c0

A的前n-1位转换到字符串B的前m-1位，这时只需要将A的最后一位修改成B的的最后一位即可。dp[i-1][j-1]+c2

dp[i][j] = min( dp[i-1][j]+c1,min(dp[i][j-1]+c0,dp[i-1][j-1]+c2));

3.确定初始状态

当i为0时，转换成B则需要添加，到第j位则添加j位，代价为j * c0

当j为0时，转换成B则需要删除，到第j位则删除j位，代价为i * c1

4.验证

当第i位和第j位相同的时候则不需要修改，d[i][j] = d[i-1][j-1] 

注意判断条件，字符串下标从0开始。

看到别人的代码，对于dp数组申请了空间，这是一个好习惯，因为堆空间比栈空间大

代码为：

//申请int **dp = new int*[n+1];for(int i=0; i