算法小课堂（四）动态规划
目录 一、概况 二、背包 2.0闫式dp分析法 2.1 0-1背包 朴素解法 滚动数组 2.2 完全背包 朴素解法 优化降维 滚动数组 2.3完全背包和0-1背包的区别与联系 2.4多重背包问题 朴素解法 二进制枚举优化 贪心算法 单调队列优化 2.5分组背包问题 朴素算法 优化降维 二进制枚举优化...
动态规划刷题记录（1）
动态规划问题在这两年蓝桥杯频繁出现，它既是一个重点，也是一个难点。 1、整数拆分 这道题目的思路其实很直接，基本上一眼就可以看出来这是完全背包问题的应用+一维优化。 整数N相当于是背包体积，2的幂相当于是物品体积，每种物品可以拿无数次，问你方案有多少种。数据范围已经给你了，我们可以确定最多用到2...
重复的DNA序列(位运算、哈希表)、括号生成(字符串、动态规划)、外出采摘的日本人(排序和顺序统计量)
重复的DNA序列(位运算、哈希表)所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s ...
POJ2151 动态规划
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int m, t, n; ][][]; ][]; double p1, p2; int main() { ...
C++ 计算直线的交点数（动态规划）
问题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1466Problem Description平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。Input输入数据包含多个测试实...
写一个动态规划的算法
写一个动态规划的算法递归是从上往下的计算，递归中有大量的重复计算，以斐波那契为例动态规划是子上往下的解决问题，先解决小数据量下的结果层层类推，解决大数据规模下的问题动态规划的思路：将原问题拆解成若干的子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。有时候自顶向下的思考问...
算法刷题-地下城游戏(数组、动态规划)、恢复二叉搜索树(树、深度优先搜索)
地下城游戏(数组、动态规划)一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即...
LeetCode HOT 100：乘积最大子数组（动态规划）
题目描述：给你一个整数数组，在该数组的所有子数组中，找到一个子数组中所有元素相乘积最大，返回这个最大的积。子数组就是一个数组中，由一个或几个下标连续的元素，组成的小数组，就叫原数组的子数组。思路：这一题和题目：53. 最大子数组和很像。但是又复杂了一点。所以建议先搞懂53题，再来看这道题。在53题曾...
【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）
【BZOJ5302】[HAOI2018]奇怪的背包（动态规划，容斥原理）题面BZOJ洛谷题解为啥泥萌做法和我都不一样啊一个重量为\(V_i\)的物品，可以放出所有\(gcd(V_i,P)\)的重量，而多个物品也只要\(gcd\)就好了。现在的问题转变成了有多少个集合\(S\)，满足\(S+\{P\}...
动态规划(Dynamic programming) 走楼梯
来自：算法爱好者有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，要求用程序来求出一共有多少种走法？f(10) = f(9) + f(8)f(9) = f(8) + f(7)f(8)= f(7)+ f(6).....................................
LeetCode -- Triangle 路径求最小和（ 动态规划问题）
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given the fol...
动态规划+滚动数组 -- POJ 1159 Palindrome
给一字符串，问最少加几个字符能够让它成为回文串。比方 Ab3bd 最少须要两个字符能够成为回文串 dAb3bAd思路：动态规划 DP[i][j] 意味着从 i 到 j 这段字符变为回文串最少要几个字符，枚举子串长。if str[i] == str[j]:DP[i][j] = DP[i + 1][j ...
UVA_1025_A_Spy_in_the_Metro_(动态规划)
描述https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466某城市的地铁是线性的,有n个车站,有M1辆列车从左到右开,M2辆列车从右...
HDU 2084 数塔（动态规划）
数塔http://acm.hdu.edu.cn/showproblem.php?pid=2084Problem Description在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？...
【原根】【动态规划】【bitset】2017四川省赛 K.2017 Revenge
题意： 给你n（不超过200w）个数，和一个数r，问你有多少种方案，使得你取出某个子集，能够让它们的乘积 mod 2017等于r。 2017有5这个原根，可以使用离散对数（指标）的思想把乘法转化成加法，然后就可以用bitset优化dp了。 裸的dp方程是f(i,j)=f(i-1,j)+f(i-1,(...
详细实例说明+典型案例实现 对动态规划法进行全面分析 | C++
第三章 动态规划法::: hljs-center目录第三章 动态规划法●前言●一、动态规划法是什么？1.简要介绍2.生活实例●二、动态规划法对斐波那契数列的优化1.优化方法2.优化核心代码片段3.代码实现以及结果展示●三、动态规划法的典型案例——最短总距离1.具体情况2.代码展示（C++...
【Luogu1345】周游加拿大（动态规划）
【Luogu1345】周游加拿大（动态规划）题面题目描述你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市...
[BJOI2019]奥术神杖（分数规划，动态规划，AC自动机）
[BJOI2019]奥术神杖（分数规划，动态规划，AC自动机）题面洛谷题解首先乘法取\(log\)变加法，开\(c\)次根变成除\(c\)。于是问题等价于最大化\(\displaystyle \frac{\sum val_i}{c}\)。典型的分数规划的形式。二分权值\(k\)，每个点的点权变成\(...
poj 2385 Apple Catching(记录结果再利用的动态规划)
传送门https://www.cnblogs.com/violet-acmer/p/9852294.html题意：有两颗苹果树，在每一时刻只有其中一棵苹果树会掉苹果，而Bessie可以在很短的时间内在两个苹果树间切换，但每一时刻只能切换一下；求在1~T时刻，Bessie在最多可以切换W次的前提下最多...
--hdu 1231 最大连续子序列(动态规划)
AC code:#include<stdio.h>int a[100005];int main(void){ int n,i; int sum,maxn,tem,s,e,flag; while(scanf("%d",&n)!=EOF,n) { ...