DP예제

#include<cstdio>
#include<iostream>

using namespace std;

int map[101][101];
int cache[101][101];
int n;

int jump(int y, int x)
{

    if (y >= n || x >= n) return 0;
    if (y == n - 1 && x == n - 1) return 1;

    int& ret = cache[y][x];

    if (ret != -1) return ret;
    int jumpSize = map[y][x];

    return ret = (jump(y + jumpSize, x) || jump(y, x + jumpSize));
}

int main()
{
    int c;

    scanf("%d", &c);

    for (int itr = 0; itr < c; itr++)
    {
        scanf("%d", &n);

        for (int i = 0; i < 101; i++)
        {
            for (int j = 0; j < 101; j++)
            {
                cache[i][j] = -1;
            }
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }

        int result = jump(0, 0);

        if (result == 1)
        {
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }

    return 0;

}

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int cache[101][101];
string W, S;

bool matchMemoized(int w, int s)
{
    int& ret = cache[w][s];
    if (ret != -1) return ret;

    while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))
    {
        ++s;
        ++w;
    }

    if (w == W.size()) return ret = (s == S.size());
    if (W[w] == '*')
    {
        for (int skip = 0; skip + s <= S.size(); ++skip)
        {
            if (matchMemoized(w + 1, s + skip))
                return ret = 1;
        }
    }

    return ret = 0;
}

int main()
{
    int c;
    cin >> c;
    for (int itr = 0; itr < c; itr++)
    {
        cin >> W;
        int num;
        cin >> num;
        for (int i = 0; i < num; i++)
        {
            for (int j = 0; j < 101; j++)
            {
                for (int k = 0; k < 101; k++)
                {
                    cache[j][k] = -1;
                }
            }

            cin >> S;
            bool result = matchMemoized(0, 0);
            if (result)
                cout << S << endl;
        }
    }

    return 0;
}