区块链技术博客
www.b2bchain.cn

[计数dp] 整数划分(模板题+计数dp+完全背包变种题)

这篇文章主要介绍了[计数dp] 整数划分(模板题+计数dp+完全背包变种题)的讲解,通过具体代码实例进行17577 讲解,并且分析了[计数dp] 整数划分(模板题+计数dp+完全背包变种题)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=17577

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 0. 前言
    • 1. 计数dp 模板题

0. 前言

计数类 dp 可分为 计数 dp 和数位统计 dp。大多是用来统计方案数什么的,特别强调 不重不漏,在此还是根据各个题的特点将计数 dp 和数位 dp 分开整理。其实数位 dp 的题目会相对多很多…

1. 计数dp 模板题

900. 整数划分

[计数dp] 整数划分(模板题+计数dp+完全背包变种题)

重点: 计数 dp完全背包问题抽象

首先模拟下样例便于理解本题:

5 = 5   = 4 + 1   = 3 + 2   = 3 + 1 + 1   = 2 + 1 + 1 + 1   = 2 + 2 + 1   = 1 + 1 + 1 + 1 + 1 共七种划分方式 

故我们可以将问题抽象为一个容量为 n 的背包,有 n 个体积为 1 ~ n 的物品,求恰好将该背包的方案数。每种物品可以使用无限次,故该问题是一个完全背包问题。

思路:

  • 状态定义:
    • f[i][j]:从 1~i 中选,且总体积恰好为 j 的选法数量
  • 状态转移:
    • 分类依据:根据最后一个物品选择个数进行状态划分,和完全背包问题的状态划分一致。
      • i 个物品选 0 个:f[i-1][j]
      • i 个物品选 1 个:f[i-1][j - i]
      • i 个物品选 2 个:f[i-1][j - 2*i]
      • i 个物品选 s 个:f[i-1][j - s*i]
    • 至此,朴素版完全背包问题就到此为止。但是,完全背包问题有一个非常厉害的优化方式。建议阅读:[背包] 背包问题算法模板(模板)
      • f[i][j] = f[i-1][j]+f[i-1][j-1]+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-i]f[i][j] 的后半段一样,故:
      • f[i][j] = f[i-1][j] + f[i][j-i]
    • 故状态转移方程为:f[i][j]=f[i-1][j]+f[i][j-i]
    • 和完全背包问题一样,也可以优化掉第一维,即 f[i]=f[j]+f[j-i]。体积从小到大循环即可
  • 状态初始化:f[0]=1,一个数都不选的方案是 1

完全背包代码:

#include <iostream> #include <algorithm>  using namespace std;  const int N = 1010, MOD = 1e9+7;  int n; int f[N];  int main() {     cin >> 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;          cout << f[n] << endl;          return 0; } 

除了完全背包的写法及状态定义外,也有一种其它的状态定义方式,状态转移方程不同但是却能得到相同的结果…

思路:

  • 状态定义:
    • f[i][j]:所有总和是 i,并且恰好表示成 j 个数的和的方案的数量
  • 状态转移:
    • 分类依据:根据表示成的这 j 个数中是否包含 1,来进行集合划分
      • 如果包含 1,等价于 f[i-1][j-1],等价于和是 i-1 数量是 j-1 的选法数量
      • 如果每个数大于 1,则等价于将这 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]
  • 状态初始化f[0][0] = 1 代表总和是 0 的时候选 0 个的方案数是 1

代码:

#include <iostream> #include <algorithm>  using namespace std;  const int N = 1010, MOD = 1e9+7;  int n; int f[N][N];  int main() {     cin >> n;          f[0][0] = 1;          for (int i = 1; i <= n; ++i)         for (int j = 1; j <= i; ++j)             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;          cout << res << endl;          return 0; } 

故可看出,同一个 dp 问题,不同的思考方式,不同的集合划分,不同的状态转移方程,只有思路是正确的,那么就是可行的。当然,在本题,划分方式不同导致了状态转移方程的不同,进而导致了求解答案时也不同。

本文转自互联网,侵权联系删除[计数dp] 整数划分(模板题+计数dp+完全背包变种题)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » [计数dp] 整数划分(模板题+计数dp+完全背包变种题)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们