DP问题分类

本文将从不同的维度解析动态规划（DP）问题的分类，并给出代码示例。

一、按照状态的维度

DP问题的状态通常需要定义，以便记录问题的解决方式。按照状态的不同维度，可以把DP问题分为以下两类：

1.一维DP

一维DP指的是，DP状态的转移只与上一次迭代有关。例如，假设我们要计算从1到n的所有数字的平方和，可以定义一个一维数组dp，dp[i]表示i的平方，那么状态转移方程为dp[i] = dp[i-1] + i*i。该问题的代码示例如下：

int square_sum(int n)
{
   vector dp(n + 1, 0); 
   for(int i = 1; i <= n; i++)
   {
        dp[i] = dp[i-1] + i*i;
   }
   return dp[n];
}

2.二维DP

二维DP指的是，DP状态的转移需要考虑i和j两个维度。例如，假设我们要在m*n的网格中，从左上角到右下角的路径，每次只能向下或向右走，求路径上数字的最小和，可以定义一个二维数组dp，dp[i][j]表示从左上角到(i,j)的数字最小和，那么状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中grid是网格状数组。该问题的代码示例如下：

int min_path_sum(vector>& grid)
{
    int m = grid.size();
    int n = grid[0].size();
    vector> dp(m, vector(n, 0));
    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++)
    {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for(int j = 1; j < n; j++)
    {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    for(int i = 1; i < m; i++)
    {
        for(int j = 1; j < n; j++)
        {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

二、按照问题类型的维度

按照问题类型的不同维度，可以把DP问题分为以下两类：

1.背包问题

背包问题是指，在一些限制条件下，选择一些物品放入背包中，使得对应的背包价值最大或最小。背包问题是DP问题中比较典型的问题之一，它可以有多种不同的变形，例如01背包、完全背包、多重背包等等。下面是一个01背包的代码示例：

int knapSack(int W, vector& wt, vector& val) {
    int n = wt.size();
    vector> dp(n+1, vector(W+1, 0));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= W; j++) {
            if(j - wt[i-1] < 0) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][W];
}

2.最长公共子序列问题

最长公共子序列问题是指，给定两个字符串s1和s2，求它们的最长公共子序列。例如，对于字符串s1="abcde"和s2="acef"，最长公共子序列为"ace"。该问题可以使用DP来求解，代码示例如下：

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    vector> dp(m+1, vector(n+1, 0));
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

三、按照DP解法的维度

按照DP解法的不同维度，可以把DP问题分为以下两类：

1.自顶向下DP

自顶向下DP通常使用递归实现，每次只考虑一个状态，并且把所有子状态都解决掉，然后求解当前状态的解。该方法存在重复计算的问题。下面是自顶向下DP的一个代码示例：

int weigth(int i, int w, vector& val, vector& wgt, vector>& memo)
{
    if (i < 0) {
        return 0;
    }
    if (memo[i][w] != -1) {
        return memo[i][w];
    }
    int res;
    if (w < wgt[i]) {
        res = weight(i - 1, w, val, wgt, memo);
    } else {
        res = max(weight(i - 1, w, val, wgt, memo), weight(i - 1, w - wgt[i], val, wgt, memo) + val[i]);
    }
    memo[i][w] = res;
    return res;
}

int knapSack(int W, vector& wt, vector& val) {
    int n = wt.size();
    vector> memo(n, vector(W+1, -1));
    return weigth(n-1, W, val, wt, memo);
}

2.自底向上DP

自底向上DP通常使用循环实现，每次需要求解的状态都已经被计算过了，不存在重复计算的问题。下面是自底向上DP的一个代码示例：

int knapSack(int W, vector& wt, vector& val) {
    int n = wt.size();
    vector> dp(n+1, vector(W+1, 0));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= W; j++) {
            if(j - wt[i-1] < 0) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][W];
}

总结

本文从状态的维度、问题类型的维度和DP解法的维度等多个方面介绍了DP问题的分类，并给出了相关的代码示例。每个DP问题都有不同的状态定义、状态转移方程和边界条件，需要根据具体情况来进行定义和解决。