动态规划-区间、计数类DP问题总结

简介: 动态规划-区间、计数类DP问题总结

什么是动态规划

动态规划通过额外的空间将已经搜索过的相似的结果(指某些具有相同性质解的集合)用一个数组存起来,所以DP中的状态转移看上去是某两三个值之间的推导,其实是某两三个集合之间的状态转移!

常见的区间DP问题

石子合并

典型题例:

设有 N 堆石子排成一排,其编号为 1,2,3,…,N。

每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2, 我们可以先合并 1、2 堆,代价为 4,得到 4 5 2, 又合并 1,2 堆,代价为 9,得到 9 2 ,再合并得到 11,总代价为 4+9+11=24;

如果第二步是先合并 2,3 堆,则代价为 7,得到 4 7,最后一次合并代价为 11,总代价为 4+7+11=22。

问题是:找出一种合理的方法,使总的代价最小,输出最小代价。

示例 :

4
1 3 5 2
输出:
22

思路

状态表示:集合f[i,j]表示所有将[i,j]合并成一堆的方法集合;属性:min

状态计算:最后一次合并肯定是[i,j]分成两堆,第一堆可以是i, i+1, i+2, ...,j-1;

枚举所有[i,j]中左右两边的堆的方法i~k, k+1~j,最后加上总代价s[j]-s[i -1]

状态转移:f[i,j] = min(f[i,j], f[i,k] + f[k+1,j] + s[j] - s[i])

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n, m;
int s[N];  //前缀和
int f[N][N];
int main() {
    cin >> n;
    //处理输入和前缀和
    for (int i = 1; i <=n; i ++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (int len = 2; len <= n; len ++)  //枚举区间长度,len=1时就是一堆
        for (int i = 1; i + len - 1 <= n; i ++) {
            int j  = i + len - 1;
            f[i][j] = 1e8;  //初始设为无穷大
            for (int k = i; k < j; k ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}

计数类DP问题

整数划分

典型题例:

一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。

示例 :

输入:
共一行,包含一个整数 n。
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对 109+7 取模。
5
输出:
7

思路

等价于完全背包问题:有一个容量为n的背包,且有n个物品,对应的体积分别为1~n,恰好装满背包的方案数

状态表示:集合f[i,j]表示所有从1~i中选,总体积恰好是j的选法的数量的集合;属性:数量

状态计算:f[i,j] = f[i-1,j] + f[i,j-i] 与完全背包优化方式一样:f[j] = f[j] + f[j-i]

代码:

#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;
    printf("%d\n", f[n]);

充电站

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

相关文章
|
8月前
|
人工智能 JSON 安全
多Agent之间个人访问凭证的安全传递问题
本文探讨多Agent场景下用户凭证安全传递的核心挑战,解析RFC 7523(JWT断言)、RFC 8693(令牌交换)及IETF AI Agent委托草案的技术方案,并以Microsoft Entra Agent ID为范例,阐述如何通过OBO流程、权限缩减、委托链审计(act声明)与企业治理实现安全、可控、可追溯的凭证委托。
1272 0
|
机器学习/深度学习 存储
数据结构(九)---并查集
数据结构(九)---并查集
857 5
|
存储 算法 API
LeetCode算法小抄 -- 经典图论算法 之 并查集算法
LeetCode算法小抄 -- 经典图论算法 之 并查集算法
|
消息中间件 安全 数据库连接
并发编程的艺术:Go语言中的Sync包技巧
并发编程的艺术:Go语言中的Sync包技巧
363 0
|
存储 算法 iOS开发
并查集详解及应用
并查集详解及应用
4139 0
【计算理论】计算复杂性 ( coNP 问题 | coNP 完全 | P、NP、coNP 相互关系 )
【计算理论】计算复杂性 ( coNP 问题 | coNP 完全 | P、NP、coNP 相互关系 )
1309 0
【计算理论】计算复杂性 ( coNP 问题 | coNP 完全 | P、NP、coNP 相互关系 )
|
编解码 算法 机器学习/深度学习
HEVC算法和体系结构:预测编码之帧内预测
<p><br></p> <h1 style="text-align:center">预测编码之帧内预测(Intra-Picture Prediction)</h1> <p><br></p> <p>        预测编码(Prediction Coding)是视频编码的核心技术之一,指利用已编码的一个或几个样本值,根据某种模型或方法,对当前的样本值进行预测,并对样本真实值和预测值之间
6360 0
|
6天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
7059 17
|
6天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2335 10
|
8天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。