笔记

栈
//stack<int> sta//创建一个栈
//sta.push(a);//入栈
//int a=sta.top();//返回栈顶元素
//sta.pop();//出栈
//sta.empty();//判断栈是否为空 1为空 0为非空
//sta.clear();//清空

队
//queue<int> que//创建一个队列
//que.push(a);//入队
//int a=que.front();//返回队头元素
//que.pop();//出队
//que.empty();//判断队列否为空 1为空 0为非空
//que.clear();//清空
优先队列
priority_queue<int> q1;//默认方式，大的优先级高
priority_queue<int,vector<int>,less<int> > q2;//大
priority_queue<int,vector<int>,greater<int> > q3; //小
q3.top();//取优先级高的元素

动态数组  vector
1.push_back  在末尾添加元素
2.pop_back 删除末尾元素
3.size  求元素个数
4.empty 判空
5.front 首元素
6.back  尾元素
7.clear 清空

集合set
#include <bits/stdc++.h>
using namespace std;
int main(){
set<int> s1;
s1.insert(1);//添加
s1.insert(1);
//s1.find();//查找
if(s1.find(1)!=s1.end()){//找到了

}
//遍历
set<int>::iterator it=s1.begin();
while(it!=s1.end()){
cout<<*it<<" ";
it++;
}
return 0;
}

映射map
#include <bits/stdc++.h>
using namespace std;
/*
map
*/
int main(){
map<string,int> maps;//定义map
maps["a"]=10;
maps["c"]=9;
maps["b"]=12;
maps["d"]=13;
maps["f"]=12;
map<string,int>::iterator it=maps.begin();
while(it!=maps.end()){
cout<<it->first<<" "<<it->second<<endl;
it++;
}
//cout<<maps["小码君"];
return 0;
}

动态规划 /* 动态规划 ：是解决最优化问题的一种策略 核心思想：枚举 1.划分阶段 以钱来划分阶段 2.确定状态 凑成不同钱的最少纸币张数 dp[i]表示凑成i块钱需要的最少张数 求的结果：dp[n] 3.状态转移方程 dp[1]=1 2<=i<=4 只解锁1块钱的 dp[i]=dp[i-1]+1 5<=i<=10 解锁1块和5块的 dp[i]=min(dp[i-1],dp[i-5])+1 拿的是1张1块 i-1 拿的是1张5块 i-5 i>=11 1，5，11都解锁了 dp[i]= dp[i-1] dp[i-5] dp[i-11]

最优子结构 无后效性：前面确定的状态，不受后面的影响，可以直接使用 重叠的子问题：

原问题：有n块钱，最少要多种张纸币凑成 先拿一张？ 子问题：有 n-拿 块钱，最少要多种张纸币凑成

子问题：拿1块钱，只有唯一的方案

*/