C语言 深入理解动态规划之计数类DP

目录
  • 写在前面
  • 石子合并

写在前面

之前讲过背包问题，线性DP，区间DP，不知道大家忘了吗，这次是计数类DP

石子合并

老规矩，先画图。

思路：把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）

初值问题：

求最大值时，当都不选时，价值显然是 0

而求方案数时，当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1

即：for (int i = 0; i <= n; i ++) f[i][0] = 1;

等价变形后： f[0] = 1

状态计算：

f[i][j]表示前i个整数（1,2…,i）恰好拼成j的方案数

求方案数：把集合选0个i，1个i，2个i，…全部加起来

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + …;

f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + …;

因此 f[i][j]=f[i−1][j]+f[i][j−i]; (这一步类似完全背包的推导）

朴素做法

// f[i][j] = f[i - 1][j] + f[i][j - i]
#include <bits/stdc++.h>

using namespace std;

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

int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; i ++) {
        f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
            if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    }

    cout << f[n][n] << endl;
}

等价变形

// f[i][j] = f[i - 1][j] + f[i][j - i]
#include <bits/stdc++.h>

using namespace std;

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

int f[N];

int main() {
    int n;
    cin >> n;

    f[0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案

    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;
}

上面是完全背包问题的解法，再来看看不用完全背包问题求解

状态计算:分两部分

  • 这j个数中存在最小值为1的数 先去掉这一个1，其他部分表示为总和为i-1,恰好由j-1个数f[i-1][j-1]
  • 这j个数中存在的最小值都>1 j个数都>1,让j个数都-1,求总和为j-i,由j个数的方案表示:f[i-j][j]

综上所述:f[i][j] = f[i - 1][j - 1] + f[i - j][j];

//非背包做法
//状态表示:f[i][j] 所有总和是i，并且恰好可以表示成j个数的和的方案
#include <bits/stdc++.h>

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 ++ )
        //i最多表示成i个数的和，因此j<=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;
}

到此这篇关于C语言 深入理解动态规划之计数类DP的文章就介绍到这了,更多相关C语言 计数类DP内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言深入探究动态规划之线性DP

    C语言深入探究动态规划之线性DP

    目录 写在前面 数字三角形 最长上升子序列 最长上升子序列 II 最长公共子序列 写在前面 之前讲过背包问题,不知道大家忘了吗,如果忘了可以点这里,这次是线性DP 数字三角形 状态表示:f[i,j],到点i,j的最大路径 状态计算:f[i,j] = MAX(f[i-1,j-1]+a[i,j],f[i-1,j]+a[i,j]) 看图,以例题为例,将它看成五行五列的三角形,每个点都可以用坐标表示.那么我们可以得知到一个数的最大路径要么来自左上,要么来自右上.左上的数用f[i-1,j-1]表示,右上的

  • C语言动态规划点杀dp算法LeetCode炒股习题案例解析

    C语言动态规划点杀dp算法LeetCode炒股习题案例解析

    目录 概念 性质 典型特征 实战论证 算法实现 优化 概念 说到动态规划,什么是动态规划? 动态规划(英语:Dynamic programming,简称 dp)通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法.动态规划常常适用于有重叠子问题和最优子结构性质的问题. 看着这么复杂哈,其实总结出来就是大事化小,拆分成小问题但是这些小问题和原问题是同质的,动规致力于解决每一个子问题,减少计算,其实和递归思想,分治法有些类似,斐波那契数列就可以看做入门级的经典动规问题 这里引用一个网上流行的例

  • C语言动态规划多种背包问题分析讲解

    C语言动态规划多种背包问题分析讲解

    目录 写在前面 01背包问题 完全背包问题 多重背包问题 I 多重背包问题 II 为什么可以这样优化呢 一 .二进制与十进制 二 .动态规划的时间复杂度估算 三 .多重背包 分组背包问题 写在前面 之前讲过简单DP,经典01背包问题,在这我将会把背包问题更深入的讲解,希望能帮助大家更好的理解. 01背包问题 C语言数学问题与简单DP01背包问题详解 先回忆一下这个图 在这我再将01背包问题代码发一遍,可以用来做对比. 二维: #include<bits/stdc++.h> using name

  • C语言 深入探究动态规划之区间DP

    C语言 深入探究动态规划之区间DP

    目录 写在前面 石子合并 写在前面 之前讲过背包问题,线性DP不知道大家忘了吗,这次是区间DP 石子合并 题意: 合并 N 堆石子,每次只能合并相邻的两堆石子,求最小代价 解题思路: 关键点:最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并 状态表示:f[i][j]表示将 i 到 j 这一段石子合并成一堆的方案的集合,属性 Min 状态计算: (1) i<j 时,f[i][j]=min f[i][k]+f[k+1][j]+s[j]−s[i−1] (2)i=j 时, f[i][i]=0

  • C语言使用DP动态规划思想解最大K乘积与乘积最大问题

    最大K乘积问题 设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定的I和k,求出I的最大k乘积. 编程任务: 对于给定的I 和k,编程计算I 的最大k 乘积. 需求输入: 输入的第1 行中有2个正整数n和k.正整数n是序列的长度:正整数k是分割的段数.接下来的一行中是一个n位十进制整数.(n<=10) 需求输出: 计算出的最大k乘积. 解题思路:DP 设w(h,k) 表示: 从第1位到第K位所组成的十进制数,设m(i,j)

  • C语言动态规划之背包问题详解

    C语言动态规划之背包问题详解

    01背包问题 给定n种物品,和一个容量为C的背包,物品i的重量是w[i],其价值为v[i].问如何选择装入背包的物品,使得装入背包中的总价值最大?(面对每个武平,只能有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入物品多次) 声明一个数组f[n][c]的二维数组,f[i][j]表示在面对第i件物品,且背包容量为j时所能获得的最大价值. 根据题目要求进行打表查找相关的边界和规律 根据打表列写相关的状态转移方程 用程序实现状态转移方程 真题演练: 一个旅行者有一个最多能装M公斤的背

  • C语言矩阵连乘 (动态规划)详解

    C语言矩阵连乘 (动态规划)详解

    动态规划法 题目描述:给定n个矩阵{A1,A2....An},其中Ai与Ai+1是可以相乘的,判断这n个矩阵通过加括号的方式相乘,使得相乘的次数最少! 以矩阵链ABCD为例 按照矩阵链长度递增计算最优值 矩阵链长度为1时,分别计算出矩阵链A.B.C.D的最优值 矩阵链长度为2时,分别计算出矩阵链AB.BC.CD的最优值 矩阵链长度为3时,分别计算出矩阵链ABC.BCD的最优值 矩阵链长度为4时,计算出矩阵链ABCD的最优值 动归方程: 分析: k为矩阵链断开的位置 d数组存放矩阵链计算的最优值,

  • C语言 深入理解动态规划之计数类DP

    C语言 深入理解动态规划之计数类DP

    目录 写在前面 石子合并 写在前面 之前讲过背包问题,线性DP,区间DP,不知道大家忘了吗,这次是计数类DP 石子合并 老规矩,先画图. 思路:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数(完全背包问题变形) 初值问题: 求最大值时,当都不选时,价值显然是 0 而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1 即:for (int i = 0; i <= n; i ++)

  • C语言 深入理解动态规划之计数类DP

    C语言 深入理解动态规划之计数类DP

    目录 写在前面 石子合并 写在前面 之前讲过背包问题,线性DP,区间DP,不知道大家忘了吗,这次是计数类DP 石子合并 老规矩,先画图. 思路:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数(完全背包问题变形) 初值问题: 求最大值时,当都不选时,价值显然是 0 而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1 即:for (int i = 0; i <= n; i ++)

  • 深入理解JVM之Class类文件结构详解

    深入理解JVM之Class类文件结构详解

    本文实例讲述了深入理解JVM之Class类文件结构.分享给大家供大家参考,具体如下: 概述 我们平时在DOS界面中往往需要运行先运行javac命令,这个命令的直接结果就是产生相应的class文件,然后基于这个class文件才可以真正运行程序得到结果.自然.这是Java虚拟机的功劳,那么是不是Java虚拟机只能编译.java的源文件呢?答案是否定的.时至今日,Java虚拟机已经实现了语言无关性的特点.而实现语言无关性的基础是虚拟机和字节码的存储格式,Java虚拟机已经不和包括Java语言在内的任何

  • 深入理解Java 对象和类

    Java作为一种面向对象语言.支持以下基本概念: •多态 •继承 •封装 •抽象 •类 •对象 •实例 •方法 •消息解析 本节我们重点研究对象和类的概念. •对象:对象是类的一个实例,有状态和行为.例如,一条狗是一个对象,它的状态有:颜色.名字.品种:行为有:摇尾巴.叫.吃等. •类:类是一个模板,它描述一类对象的行为和状态. Java中的对象 现在让我们深入了解什么是对象.看看周围真实的世界,会发现身边有很多对象,车,狗,人等等.所有这些对象都有自己的状态和行为. 拿一条狗来举例,它的状态有

  • ThinkPHP进程计数类Process用法实例详解

    本文实例讲述了ThinkPHP进程计数类Process用法.分享给大家供大家参考.具体如下: 项目中有一个需求:由于某一后台任务比较占带宽,所以要限制进程数.花了点时间,写了类,目前版本功能比较简单. Process.class.php文件如下: <?php /** * Process * * @package * @version $id$ * @copyright 2005-2011 SUCOP.COM * @author Dijia Huang <huangdijia@gmail.com

  • 深入理解java.lang.String类的不可变性

    深入理解java.lang.String类的不可变性

    1. 字符串 String 的不可变性 什么是不可变类? 这样理解:         一个对象在创建完成后,不能去改变它的状态,不能改变它的成员变量(如果成员变量包含基本数据类型,那么这个基本数据类型的值不能改变:如果包含引用类型,那么这个引用类型的变量不能指向别的对象) 不可变类只是其实例不能被修改的类.每个实例中包含的所有信息都必须在创建该实例的时候就提供,并且在对象的整个生命周期内固定不变.为了使类不可变,要遵循下面五条规则: 不要提供任何会修改对象状态的方法 保证类不会被扩展. 一般的做

  • c语言 深入理解函数的递归

    前言:  首先,递归是什么,递归就是在定义函数时,然后在函数里调用这个函数,通俗讲,就是函数自己调用自己.那么递归的好处是什么呢?它能够将复杂的问题,用少量的代码来表示,增加了代码的可读性. 但是递归有一个条件,就是每一次的重复调用都需要越接近这个限制条件. 1.用递归打印一个整数的每一位 题目的要求是打印一个整数的每一位,就比如说1234,打印的结果就是1234,我们学过用循环打印过4321,但顺着打印,用循环来做,相对于递归来解,就会有点复杂. #include<stdio.h>//打印一

  • C语言 从根本上理解指针

    C语言 从根本上理解指针

    目录 一.* 的意义 二.传值调用与传址调用 三.常量与指针 四.小结 一.* 的意义 在指针声明时,* 号表示所声明的变量为指针 在指针使用时,* 号表示取指针所指向的内存空间中的值 如下: int i = 0; int j = 0; int* p = &i; //指针声明 j = *p; //取值 变量 p 保存着变量 i 的内存地址,即:p <--> &i *p <--> i * 号类似一把钥匙,通过这把钥匙可以打开内存,读取内存中的值. 下面看一个指针的使用

随机推荐