}
}
return dp[n-1][m-1];
}
};
上面的方法中初始化第一行和第一列有点麻烦,增加了额外的语句,可以增加数组一行和一列来优化代码:
class LCS {
public:
int findLCS(string A, int n, string B, int m) {
vector<vector<int> > dp(n+1,vector<int>(m+1,0));
for (int i =1;i<=n ;++i){
for (int j=1; j<=m; ++j){
if (A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1]+1; //第1行也可以照此直接初始化
}
else {
dp[i][j] = max( dp[i-1][j] ,dp[i][j-1]);
}
}
}
return dp[n][m];
}
};
问题6:背包
N件物品,价值记录在数组V,重量记录在数组W,背包总重量最大为cap,要求总价值最大;
class Backpack {
public:
int maxValue(vector<int> w, vector<int> v, int n, int cap) {
if (w.empty()||v.empty()||n==0||cap==0)
return 0;
vector<vector<int> > dp(n,vector<int>(cap+1));
for (int j = 1;j < cap+1;j++) {
dp[0][j] = w[0] <= j?v[0]:0;
}
for (int i = 0;i < n;i++) {
dp[i][0] = 0;
}
for (int i = 1;i < n;i++) {
for (int j = 1;j < cap+1;j++) {
if (w[i] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]); //由于该问题每个物品最多只能放1件,如果不限制个数的话,则在这里修改条件
}
}
return dp[n-1][cap];
}
};
由于没有用到斜侧的比较,所以可以使用1维的数组:
class Backpack {
public:
int maxValue(vector<int> w, vector<int> v, int n, int cap) {
if (w.empty()||v.empty()||n==0||cap==0)
return 0;
vector<int> dp(cap+1,0);
for (int i = 0;i < n;i++) {
vector<int> last(dp);
for (int j = 1;j < cap+1;j++) {
dp[j] = j < w[i]?last[j]:max(last[j],v[i]+last[j-w[i]]);
}
}
return dp[cap];