[Algo] 二维动态规划

fx1 - 暴力递归, fx2 - 记忆化搜索, fx3 - 严格位置依赖, fx4 - 状态压缩

1. 最小路径和

// 1. 最小路径和
// https://leetcode.cn/problems/minimum-path-sum/description/
int f11(vector<vector<int>>& grid, int i, int j)
{
    int n = grid.size(), m = grid[0].size();
    if (i == n - 1 && j == m - 1) return grid[i][j];
    int down = i + 1 >= n ? INT32_MAX : f11(grid, i + 1, j);
    int right = j + 1 >= m ? INT32_MAX : f11(grid, i, j + 1);
    return grid[i][j] + min(down, right);
}
int f12(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& mem)
{
    int n = grid.size(), m = grid[0].size();
    if (mem[i][j] != -1) return mem[i][j];
    int ans;
    if (i == n - 1 && j == m - 1) ans = grid[i][j];
    else
    {
        int down = i + 1 >= n ? INT32_MAX : f12(grid, i + 1, j, mem);
        int right = j + 1 >= m ? INT32_MAX : f12(grid, i, j + 1, mem);
        ans = grid[i][j] + min(down, right);
    }
    mem[i][j] = ans;
    return ans;
}
int f13(vector<vector<int>>& grid, vector<vector<int>>& dp)
{
    // 每个格子依赖右边和下面的格子，因此从下往上，从右往左依次填充dp表
    int n = grid.size(), m = grid[0].size();
    dp[n - 1][m - 1] = grid[n - 1][m - 1];
    for (int j = m - 2; j >= 0; j--) dp[n - 1][j] = dp[n - 1][j + 1] + grid[n - 1][j];
    for (int i = n - 2; i >= 0; i--) dp[i][m - 1] = dp[i + 1][m - 1] + grid[i][m - 1];
    for (int i = n - 2; i >= 0; i--)
    for (int j = m - 2; j >= 0; j--) dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
    return dp[0][0];
}
int f14(vector<vector<int>>& grid, vector<int>& dp)
{
    // 根据位置依赖关系，dp表可以压缩成单行
    int n = grid.size(), m = grid[0].size();
    dp[m - 1] = grid[n - 1][m - 1];
    for (int j = m - 2; j >= 0; j--) dp[j] = dp[j + 1] + grid[n - 1][j];
    for (int i = n - 2; i >= 0; i--)
    {
        dp[m - 1] = dp[m - 1] + grid[i][m - 1];
        for (int j = m - 2; j >= 0; j--) dp[j] = grid[i][j] + min(dp[j], dp[j + 1]);
    }
    return dp[0];
}
int minPathSum(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<int> dp(m);
    return f14(grid, dp);
}

2. 最长公共子序列

// 2. 最长公共子序列
// https://leetcode.cn/problems/longest-common-subsequence/description/
int f21(string &s1, string &s2, int len1, int len2)
{
    if (len1 == 0 || len2 == 0) return 0;
    if (s1[len1 - 1] == s2[len2 - 1]) return 1 + f21(s1, s2, len1 - 1, len2 - 1);
    else return max(f21(s1, s2, len1 - 1, len2), f21(s1, s2, len1, len2 - 1));
}
int f22(string &s1, string &s2, int len1, int len2, vector<vector<int>> &mem)
{
    if (mem[len1][len2] != -1) return mem[len1][len2];
    int ans;
    if (len1 == 0 || len2 == 0) ans = 0;
    else if (s1[len1 - 1] == s2[len2 - 1]) ans = 1 + f22(s1, s2, len1 - 1, len2 - 1, mem);
    else ans = max(f22(s1, s2, len1 - 1, len2, mem), f22(s1, s2, len1, len2 - 1, mem));
    mem[len1][len2] = ans;
    return ans;
}
int f23(string &s1, string &s2, vector<vector<int>> &dp)
{
    // 每个格子依赖左边、上面和左上的三个格子，因此从上往下，从左往右填充dp表
    int len1 = s1.length(), len2 = s2.length();
    for (int i = 1; i <= len1; i++)
    for (int j = 1; j <= len2; j++)
    {
        if (s1[i - 1] == s2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
    return dp[len1][len2];
}
int f24(string &s1, string &s2, vector<int> &dp)
{
    // 由于每个格子除了依赖左边和上面的格子外，还需要依赖左上的格子，因此需要多用一个变量leftup保存左上的值
    int len1 = s1.length(), len2 = s2.length();
    for (int i = 1; i <= len1; i++)
    {
        int leftup = 0, tmp;
        for (int j = 1; j <= len2; j++)
        {
            tmp = dp[j];
            if (s1[i - 1] == s2[j - 1]) dp[j] = 1 + leftup;
            else dp[j] = max(dp[j - 1], dp[j]);
            leftup = tmp;
        }
    }
    return dp[len2];
}
int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.length(), len2 = text2.length();
    if (len1 < len2)
    {
        vector<int> dp(len1 + 1);
        return f24(text2, text1, dp);
    }
    else
    {
        vector<int> dp(len2 + 1);
        return f24(text1, text2, dp);
    }
}

3. 节点数为n高度不大于m的二叉树个数

// 3. 节点数为n高度不大于m的二叉树个数
// https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea
long f31(int n, int m)
{
    if (n == 0) return 1;
    if (m == 0) return 0;
    // n > 0, m > 0
    long ans = 0;
    for (int k = 0; k <= n - 1; k++) ans = (ans + (f31(k, m - 1) * f31(n - 1 - k, m - 1)) % MOD) % MOD;
    return ans;
}
long f32(int n, int m, vector<vector<long>> &mem)
{
    if (mem[n][m] != -1) return mem[n][m];
    long ans = 0;
    if (n == 0) ans = 1;
    else if (m == 0) ans = 0;
    // n > 0, m > 0
    else for (int k = 0; k <= n - 1; k++) ans = (ans + (f32(k, m - 1, mem) * f32(n - 1 - k, m - 1, mem)) % MOD) % MOD;
    mem[n][m] = ans;
    return ans;
}
long f33(int n, int m, vector<vector<long>> &dp)
{
    for (int j = 0; j <= m; j++) dp[0][j] = 1;
    for (int i = 1; i <= n; i++) dp[i][0] = 0;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    for (int k = 0; k <= i - 1; k++)
    dp[i][j] = (dp[i][j] + (dp[k][j - 1] * dp[i - 1 - k][j - 1]) % MOD) % MOD;
    return dp[n][m];
}
long f34(int n, int m, vector<long> &dp)
{
    dp[0] = 1;
    for (int j = 1; j <= m; j++)
    for (int i = n; i >= 1; i--)
    {
        dp[i] = 0; // !!!
        for (int k = 0; k <= i - 1; k++)
        dp[i] = (dp[i] + (dp[k] * dp[i - 1 - k]) % MOD) % MOD;
    }
    return dp[n];
}
int numberOfBinaryTree(int n, int m)
{
    vector<long> dp(n + 1);
    return f34(n, m, dp);
}