动态规划练习 10-白红宇

动态规划练习 10

阅读量：6699 次

发布时间：2019-06-25

本文共 1341 字，大约阅读时间需要 4 分钟。

题目：Zipper (POJ 2192)

链接：

#include 
#include 
#include 
 
using namespace std;
 
bool dp[201][201];
 
// Recursion version.
bool check_yes(const string &a, size_t i, const string &b, size_t j, const string &c, size_t k)
{
if (k >= c.size())
{
return true;
}
 
bool ret1 = false, ret2 = false;
 
if (i < a.size() && c[k] == a[i])
{
ret1 = check_yes(a, i + 1, b, j, c, k + 1);
}
 
if (j < b.size() && c[k] == b[j])
{
ret2 = check_yes(a, i, b, j + 1, c, k + 1);
}
 
return ret1 || ret2;
}
 
int main(int argc, char **argv)
{
int n;
string a, b, c;
 
cin >> n;
 
for (int m = 1; m <= n; ++m)
{
cin >> a >> b >> c;
 
// Recursion version.
// cout << check_yes(a, 0, b, 0, c, 0) << endl;
// dp[i][j] = (dp[i - 1][j] && a[i - 1] == c[i + j - 1]) ||
//            (dp[i][j - 1] && b[j - 1] == c[i + j - 1]);
 
memset(dp, 0, sizeof(dp));
 
dp[0][0] = true;
 
for (size_t i = 1; i <= a.size(); ++i)
{
dp[i][0] = dp[i - 1][0] && a[i - 1] == c[i - 1];
}
 
for (size_t j = 1; j <= b.size(); ++j)
{
dp[0][j] = dp[0][j - 1] && b[j - 1] == c[j - 1];
}
 
for (size_t i = 1; i <= a.size(); ++i)
{
for (size_t j = 1; j <= b.size(); ++j)
{
dp[i][j] = (dp[i - 1][j] && a[i - 1] == c[i + j - 1])
|| (dp[i][j - 1] && b[j - 1] == c[i + j - 1]);
}
}
 
cout << "Data set " << m << ": " <<
(dp[a.size()][b.size()] ? "yes" : "no") << endl;
}
 
return 0;
}