[ACM学习] 动态规划基础之一二三维dp

这篇具有很好参考价值的文章主要介绍了[ACM学习] 动态规划基础之一二三维dp。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

课内学习的动态规划

有记忆的迭代

优化解的结构:原始问题的一部分解是子问题的解

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

三要素:1.子问题 2.状态的定义 3.状态转移方程 

定义

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

线性dp的一道例题

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

dp[i]表示以位置 i 结尾的方案总数,dp[4]=2,因为:首先只放一个4是可以的,4的位置之前还可以放1,我们不需要知道1之前还可以放什么数,只需要知道1的方案数加上4也是 dp[4] 的一部分方案数。

记得用前缀和来维护所有可行的方案。

二维dp

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

经验:列常常是1到结果、行常常是是否把这个选项 i 放入考虑范围

例题

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

首先:为什么用二维dp:对于选择,不能用一条线来解决,需要用一个从1到n的数组,来存储:把第一个选项纳入考虑(只是考虑,不是真放了),到把前 i 个纳入考虑(方便我们在上一个的基础上解决下一个) 

注意这里的列坐标是从 1 到 64 ,不是1到x,因为可以由一个比x更大的数异或 ai 后,结果是x,所以我们有必要保存比x大的数,(64的由来:每个进行异或的数大小不超过63,即11111111,所以进行异或和的结果也肯定不会超过11111111,即63)

附上代码

#include <iostream>
using namespace std;

const int N = 1e5+5;
const int p = 998244353;
int dp[N][70];
int a[N];

int main()
{
  // 请在此输入您的代码
  int n,x;
  cin >> n >> x;
  for(int i = 1 ; i <= n ; i++){
    cin >> a[i];
  }
  dp[0][0]=1;
  for(int i = 1 ; i <= n ; i++){
    for(int j = 0 ; j <= 64 ; j++){
      dp[i][j] = (dp[i-1][j]+dp[i-1][j^a[i]])%p;
    }
  }
  cout << dp[n][x];

  return 0;
}

注意:什么样的数字异或 ai 后是 j ?   ---  j ^ ai 这个数字(这就要用到异或 j ^ ai ^ ai = j)

三维dp例题

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法

多一个条件就多了一个维度,来记录k次位移。

附上代码

[ACM学习] 动态规划基础之一二三维dp,学习,动态规划,算法文章来源地址https://www.toymoban.com/news/detail-791232.html

到了这里,关于[ACM学习] 动态规划基础之一二三维dp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(42)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(51)
  • 动态规划算法学习一:DP的重要知识点、矩阵连乘算法

    三部曲如下三步: 基本原则:“空间换时间” 存储重复子问题的解,减少运算时间 底层运算:“表格操作” 用表格存储子问题的解 实现路线:“子问题划分、自底向上求解” 利用表格中存储的子问题的解,求上一层子问题的解。 矩阵连乘计算次序 可以用 加括号的方式

    2024年02月09日
    浏览(41)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(51)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(57)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(50)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(47)
  • 【动态规划】基础DP--硬币组合

    动态规划(Dynamic Programming,DP)一般是多阶段决策问题,把一个复杂问题分解为相对简单的子问题,再一一解决,得到原复杂问题的最优解。 求解DP问题的步骤:定义状态、状态转移、算法实现。 DP问题可以分为线性和非线性的。 线性DP。线性DP有两种方法:顺推与逆推。在

    2024年02月07日
    浏览(39)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包