第一章 动态规划(11)：计数DP模型、记忆化搜索模型

• 一、计数DP模型
• • 1.1 整数划分
• 二、记忆化搜索模型
• • 2.1 滑雪

ACWing 900

算法思路一：看成完全背包问题

有一个容量为n的背包，然后有n个物品，每个物品的体积分别是1、2、3 ... n，每种物品的数量不限，求恰好装满背包的方案数。

集合
f(i,j)：从物品1~i中选择，使总体积恰好等于j的选择的数量

集合分类
从第i个物品中最多选择多少个来划分：

状态计算

• 选择0个：f[i-1, j];
• 选择1个：f[i-1, j-i]；
• 选择2个：f[i-1, j-2i]；
• …
• 选择s个：f[i-1, j-s*i]。

因此，有f[i, j] = f[i-1, j] + f[i-1, j-i] + f[i-1, j-i*2] + ... + f[i-1, j-i*s]。

解释一下，举个栗子：
比如当s=2时，表示从1 ~ i中选择了2个i，使其总体积恰好等于j，其方案数就等价于从1 ~ i-1中选择2个i，其总体积恰好等于j - 2*i。

优化

f[i, j] = f[i-1, j] + f[i-1, j-i] + f[i-1, j-i*2] + ... + f[i-1, j-i*s]
f[i, j-i] =           f[i-1, j-i] + f[i-1, j-i*2] + ... + f[i-1, j-i*s]
由上可知：f[i, j] = f[i-1, j] + f[i, j-i]

#include 
#include 

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
    scanf("%d", &n);
    
    
    
    
    
    f[0] = 1;
    
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;
    
    printf("%dn", f[n]);
    
    return 0;
} 

算法思路二：

集合
f(i,j)：所有总和是i，并且恰好表示成j个数的和的方案

集合划分

f[i, j]：总和是i，并且恰好表示成j个数的和的方案数量

• ①：总和是i，表示成j个数的和，并且每个方案的最小值都是1的方案集合。因为每个方案中都有一个1，如果将每个方案中的1去掉，则表示成和是 i - 1，j - 1 个数的和，即f[i-1, j-1]；
• ②：总和是i，表示成j个数的和，并且每个方案的最小值都大于1的方案集合。因为每个数都是大于1的，所以将每个数都减去1，每个数仍然大于等于1，即仍然是一个正整数，表示为f[i-j*1, j] = f[i-j, j]；

状态计算

• f[i, j] = f[i-1, j-1] + f[i-j, j];
• ans = f[n, 1] + f[n, 2] + .. + f[n, n];

#include 
#include 

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    scanf("%d", &n);
    
    f[0][0] = 1; // 总和是0，用0个数来表示，方案数是1
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ ) // i最多表示成i个数的和
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
            
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = (res + f[n][i]) % mod;
        
    printf("%dn", res);
    
    return 0;
}

ACWing 901

集合
f[i, j]：所有从[i, j]开始滑的路径长度的最大值

集合划分与状态计算
按上一个格子滑到当前格子[i, j]的方向来划分：

• 从上面滑过来：f[i-1][j] + 1
• 从下面滑过来：f[i+1][j] + 1
• 从右边活过来：f[i][j+1] + 1
• 从左边滑过来：f[i][j-1] + 1
  

我们在计算的时候不能是环形，即图是拓扑图。因为题中要求后一个状态的高度要小于前一个状态的高度，所以一定不存在环。

#include 
#include 
#include 

using namespace std;

const int N = 310;

int n, m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;
    
    v = 1; 
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }
    
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &h[i][j]);
            
    memset(f, -1, sizeof f); // 初始化，表示每个结点都没有算过
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));
            
    printf("%dn", res);
    
    return 0;
}