基本流程

1. 找到暴力递归写法（尝试）
2. 若有重复解
3. 根据可变参数构造缓存
4. 不讲究组织，直接进行缓存-》记忆化搜索
5. 讲究组织-》经典动态规划

实例

暴力递归改记忆化搜索

int process9(int N, int m, int k, int P, int **dp)
{
    if (dp[m][k] != -1)
    {
        return dp[m][k];
    }

    if (k == 0)
    {
        if (m == P)
        {
            dp[m][k] = 1;
            return dp[m][k];
        }
        else
        {
            dp[m][k] = 0;
            return dp[m][k];
        }

    }
    int methods = 0;
    if (k >= 1)
    {
        if (m == 1)
        {
            methods += process9(N, m + 1, k - 1, P, dp);
        }
        else if (m == N)
        {
            methods += process9(N, m - 1, k - 1, P, dp);
        }
        else
        {
            methods += process9(N, m - 1, k - 1, P, dp);
            methods += process9(N, m + 1, k - 1, P, dp);
        }
    }
    dp[m][k] = methods;
    return methods;
}

int test6(int N, int M, int K, int P)
{
    int** dp = new int* [N + 1];
    for (int i = 1; i < N + 1; ++i)
    {
        dp[i] = new int[K + 1];
    }

    for (int i = 1; i < N + 1; ++i)
    {
        for (int j = 0; j < K + 1; ++j)
        {
            dp[i][j] = -1;
        }
    }

    int res = process9(N, M, K, P, dp);

    for (int i = 1; i < N + 1; ++i)
    {
        delete[] dp[i];
    }
    delete[] dp;

    return  res;

}

暴力递归改经典动态规划

int test1(const int weights[], const int values[], int bag, int n)
{
    vector<vector<int>> dp(n + 1, vector<int>(bag + 1, 0));
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = 0; j <= bag; ++j)
        {
            int p1 = -1;
            int p2 = -1;
            if (weights[i] <= j)
            {
                p1 = values[i] + dp[i + 1][j - weights[i]];
            }
            p2 = dp[i + 1][j];
            dp[i][j] = max(p1, p2);
        }
    }
    return dp[0][bag];   
}

int test2(const vector<int>& arr)
{
    int n = arr.size();
    vector<vector<int>> dp_f(n, vector<int>(n, 0));
    vector<vector<int>> dp_s(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i)
    {
        dp_f[i][i] = arr[i];
        dp_s[i][i] = 0;
    }
    for (int i = 1; i < n; ++i)
    {
        int l = 0;
        int r = i;
        while (r < n && l < n)
        {
            dp_f[l][r] = max(arr[l] + dp_s[l + 1][r], arr[r] + dp_s[l][r - 1]);
            dp_s[l][r] = min(dp_f[l + 1][r], dp_f[l][r - 1]);
            ++r;
            ++l;
        }
    }
    return max(dp_f[0][n - 1], dp_s[0][n - 1]);
}