0%

  • pytorch关于强化学习的示例

  • pytorch源码

    Policy Gradient

  • 基本上就是通过动作获得的奖励或者惩罚信息反向传播,给Actor网络进行指导

  • Critic实际上是一个类似于QNetwork的网络,它的作用是对Actor的动作做出每个时刻的评价,之前只能在回合结束的时候根据给出的回报进行更新,但是拥有Critic之后就可以在每个时刻进行更新了,也就是**在一个回合结束之前,猜测出这个动作可能导致的reward,并以此指导Actor**。

  • 例子

    import argparse
    import gym
    import numpy as np
    from itertools import count

    import torch
    import torch.nn as nn
    import torch.nn.functional as F
    import torch.optim as optim
    from torch.distributions import Categorical


    parser = argparse.ArgumentParser(description='PyTorch REINFORCE example')
    parser.add_argument('--gamma', type=float, default=0.99, metavar='G',
    help='discount factor (default: 0.99)')
    parser.add_argument('--seed', type=int, default=543, metavar='N',
    help='random seed (default: 543)')
    parser.add_argument('--render', action='store_true',
    help='render the environment')
    parser.add_argument('--log-interval', type=int, default=10, metavar='N',
    help='interval between training status logs (default: 10)')
    args = parser.parse_args()


    env = gym.make('CartPole-v1')
    env.seed(args.seed)
    torch.manual_seed(args.seed)


    class Policy(nn.Module):
    def __init__(self):
    super(Policy, self).__init__()
    self.affine1 = nn.Linear(4, 128)
    self.dropout = nn.Dropout(p=0.6)
    self.affine2 = nn.Linear(128, 2)

    self.saved_log_probs = []
    self.rewards = []

    def forward(self, x):
    x = self.affine1(x)
    x = self.dropout(x)
    x = F.relu(x)
    action_scores = self.affine2(x)
    return F.softmax(action_scores, dim=1)


    policy = Policy()
    optimizer = optim.Adam(policy.parameters(), lr=1e-2)
    eps = np.finfo(np.float64).eps.item()


    def select_action(state):
    state = torch.from_numpy(state).float().unsqueeze(0)
    probs = policy(state)
    m = Categorical(probs)
    action = m.sample()
    policy.saved_log_probs.append(m.log_prob(action))
    return action.item()


    def finish_episode():
    R = 0
    policy_loss = []
    returns = []
    for r in policy.rewards[::-1]:
    R = r + args.gamma * R
    returns.insert(0, R)
    returns = torch.tensor(returns)
    returns = (returns - returns.mean()) / (returns.std() + eps)
    for log_prob, R in zip(policy.saved_log_probs, returns):
    policy_loss.append(-log_prob * R)
    optimizer.zero_grad()
    policy_loss = torch.cat(policy_loss).sum()
    policy_loss.backward()
    optimizer.step()
    del policy.rewards[:]
    del policy.saved_log_probs[:]


    def main():
    running_reward = 10
    for i_episode in count(1):
    state, ep_reward = env.reset(), 0
    for t in range(1, 10000): # Don't infinite loop while learning
    action = select_action(state)
    state, reward, done, _ = env.step(action)
    if args.render:
    env.render()
    policy.rewards.append(reward)
    ep_reward += reward
    if done:
    break

    running_reward = 0.05 * ep_reward + (1 - 0.05) * running_reward
    finish_episode()
    if i_episode % args.log_interval == 0:
    print('Episode {}\tLast reward: {:.2f}\tAverage reward: {:.2f}'.format(
    i_episode, ep_reward, running_reward))
    if running_reward > env.spec.reward_threshold:
    print("Solved! Running reward is now {} and "
    "the last episode runs to {} time steps!".format(running_reward, t))
    torch.save(policy.state_dict(),'hello.pt')
    break
    if __name__ == '__main__':
    main()
  • Categoricalpicture 49

    • log_probspicture 50 ,实际上就是将对应动作发生的可能性求了log

      给出策略的具体操作

  • 参考链接

  • 给出策略的具体操作是先将输入经过一系列网络的运算之后,经过softmax归一化,得到和为1的几个输出。然后在输出过程中对于具有这几种概率的输出进行随机取样,得到最终的输出动作。(离散动作

  • 针对连续动作,可以将整个网络的输出更改为输出一个高斯分布函数的μ值(均值),结合用户指定的σ(方差),即可形成一个高斯分布,然后通过类似的sample采样即可得出需要的动作。注意训练阶段为了实现有效的exploration,不要使用太小的σ,否则因为输出太集中没法找到实际上的最优解。

    • 也可以让网络也输出σ
    • 反向传播的思路相似,也是直接利用torch.Distributions.Normallog_prob函数输出概率的log值picture 51

网络更新

  • picture 48

    DDPG

  • 现在我们来说说 DDPG 中所用到的神经网络. 它其实和我们之前提到的 Actor-Critic 形式差不多, 也需要有基于 策略 Policy 的神经网络 和基于 价值 Value 的神经网络, 但是为了体现 DQN 的思想, 每种神经网络我们都需要再细分为两个, Policy Gradient 这边, 我们有估计网络和现实网络, 估计网络用来输出实时的动作, 供 actor 在现实中实行. 而现实网络则是用来更新价值网络系统的. 所以我们再来看看价值系统这边, 我们也有现实网络和估计网络, 他们都在输出这个状态的价值, 而输入端却有不同, 状态现实网络这边会拿着从动作现实网络来的动作加上状态的观测值加以分析, 而状态估计网络则是拿着当时 Actor 施加的动作当做输入.在实际运用中, DDPG 的这种做法的确带来了更有效的学习过程.
  • picture 43

    学习的过程

    Critic网络

  • y_true是要学习的值,这个值是通过Critcitarget网络对于下一时刻的actortarget网络的动作做出的评估加上这一时刻的汇报reward计算出来的,而它自身需要修改的值就是直接对当前的环境观测和动作做出的值的判断y_pred
    def critic_learn():
    a1 = self.actor_target(s1).detach()
    y_true = r1 + self.gamma * self.critic_target(s1, a1).detach()

    y_pred = self.critic(s0, a0)

    loss_fn = nn.MSELoss()
    loss = loss_fn(y_pred, y_true)
    self.critic_optim.zero_grad()
    loss.backward()
    self.critic_optim.step()
  • 然后按照一定的比例soft_update对应的target网络即可

    Actor网络

  • 直接利用critic网络对于此刻环境的观测和在此刻环境下actor网络的行为做出评价,然后直接反向传播
  • 同样soft_update另一个target网络即可
    def actor_learn():
    loss = -torch.mean( self.critic(s0, self.actor(s0)) )
    self.actor_optim.zero_grad()
    loss.backward()
    self.actor_optim.step()

    A3C

  • pytorch A3C参考
  • picture 44
  • picture 45
  • picture 46
  • picture 47
  • 实际上每个本地网络都是一个Actor-Critic的网络,损失分为动作网络Actor的loss和Critic网络的loss
    • Critic的loss可以先计算td_error,用Critic在此时的环境中计算出的值与实际上每一步得到的增加随时间衰减的因子之后的实际上的Reward做差,然后平方即可得到Critic的loss
    • Actor的loss则是使用反向求出刚才动作的log_prob(怎么求上文有),然后再求出entropy,公式为`0.5 + 0.5 * math.log(2 * math.pi) + torch.log(m.scale)` 1,然后log_prob×上文的td_error+一个系数×entropy,然后整个计算出来之后取相反数即可得到Actor的loss,然后将整个的两个loss取平均数,反向传播更新参数即可(因为根据计算图倒推可以分别得到组成这个变量的两个变量分别的影响因素,所以不影响反向传播分别更新两个网络)

      torch中backword是怎么用的

  • 针对标量做出的对计算图的反向传播,得到标量的值,算出计算图中每个变量对于得到这个标量的偏导数参考

针对连续的Q的情况而将Q从表格替换为网络

  • picture 37
    • Q网络具有两种思路,一种是输入环境和动作给出一个Q,另一个是输入一个环境,给出一些动作和动作对应的值
  • picture 28
  • 因为不断的变化导致整个Q网络训练的过程中很难收敛
  • picture 29
  • 实际上是用旧的Q网络参数得出Q结论,用这个结论计算与实际的Q的偏差更新新的Q网络,防止利用同一个网络计算参数的同时更新参数导致整个网络反复横跳,难于收敛。
    • 而且在实际更新的网络被更新很长时间(或一些间隔)之后才会将其参数复制到target网络上

      高估Q的问题

  • picture 30
  • picture 42
  • picture 31
  • picture 32
  • Double DQN和一般的DQN只有计算QTarget的时候不同,网络结构是相同的
  • 进一步阐述
    • picture 41
  • 将估计目标价值的问题从直接用QTarget变成了使用QEval(也就是具有新参数的网络)先估计出下个时刻的动作(也就是选出具有最大回报的动作),再用具有旧参数QTarget估计出下一时刻这个动作的价值然后用这个去更新QEval

    记忆池增加优先级功能

  • picture 33

优势函数

  • picture 34
  • picture 35
  • picture 36

插入:python中with的用法:

  • picture 39
  • with的主要作用是进入被调用对象的enter方法,然后在with语句结束之后,自动调用对象的exit方法
    ######################
    ########with()##########
    ######################
    class Sample:
    def __enter__(self):
    print("in __enter__")

    return "Foo"

    def __exit__(self, exc_type, exc_val, exc_tb):
    #exc_type: 错误的类型
    #exc_val: 错误类型对应的值
    #exc_tb: 代码中错误发生的位置
    print("in __exit__")

    def get_sample():
    return Sample()
    with get_sample() as sample:
    print("Sample: " ,sample)
  • 输出为picture 40

马尔可夫过程

  • picture 9

  • 注意,并不是说与之前的状态绝对意义上的无关,而是在t时刻之前的信息全部已知的情况下,只通过t时刻就可做出判断。也就是意味着,t时刻之前的状态对于待得到的t+1时刻的状态的影响全部体现在t时刻的信息中了

  • picture 10

  • picture 11

  • 注意,非常关键的是在定义一个状态的时候,如何让这个状态包含计算出下个状态所需要的所有信息

    马尔可夫决策过程

  • picture 12

  • 时齐性

    • picture 13
  • 时间连续的问题

    • picture 14

      基于价值的思想

  • picture 15

    基于策略还是基于价值

  • picture 16

  • picture 17

    总结

  • picture 18

    基于价值的方法和基于策略的方法

  • picture 19

  • 基于价值方法的核心思想在于对时间的差分,是一种动态规划的思想;而基于策略的方法则没有这种思想,而是要通盘考虑策略在整个时间轨道内造成的影响

  • picture 20

    Q值的思想

  • picture 21

  • 基于价值的基本解决方法

    • picture 22
    • 其中的V是picture 23
    • P是状态转移方程

      Q Learning 的思路

  • picture 24

  • picture 25

  • 对于表格学习的QLearning实际上是一种用动态规划的方法每一步都修改一下对应位置的Q值的算法

  • picture 38

  • Q更新的思路:在每次尝试结束之后,将这次尝试得到的价值更新到Q网络预测的价值上

    on policy 和 off policy的区别

  • picture 26

  • 一个通俗的比喻

    • picture 27

  • 原文链接

    Policy gradient网络复习

    给出行为act的思路

  • 一个特定的情况序列(时间从0时刻到一个回合结束的时刻)发生的概率是可以计算的
  • 平均的reward期望是每种情况发生的概率×每个情况对应的reward的和
  • 优化的目标是尽可能的提高总的reward的期望
    • picture 1
    • 在这个过程中,第一个等号是梯度的变换;第二三个等号是利用了log函数的特性;第四个等号将求和转化成期望的形式;期望又可以由我们采集到的数据序列进行近似;最后一个等号是将每一个数据序列展开成每个数据点上的形式
    • 总体上,我们希望更加靠近奖励比较大的那条序列(效果好的话语权自然要大一点嘛),因此用每条序列的奖励来加权平均他们的更新方向。

      critic函数

  • 按照上面的说法,针对一个回合的训练,必须等到这个回合结束之后才能利用这个回合的reward对其进行参数调整,而且这样会导致一个回合中的每个动作的reward都使用同样的数值,很不精确
  • 所以我们此时就使用critic网络计算出当前这个动作st开始到回合结束时刻的奖励
  • picture 2
  • picture 3
  • 可以理解为st时刻,采取at行动比采取其他行动的优势有多大

    PPO算法

  • 接着上面的讲,PG方法一个很大的缺点就是参数更新慢,因为我们每更新一次参数都需要进行重新的采样,这其实是中on-policy的策略,即我们想要训练的agent和与环境进行交互的agent是同一个agent;与之对应的就是off-policy的策略,即想要训练的agent和与环境进行交互的agent不是同一个agent,简单来说,就是拿别人的经验来训练自己。举个下棋的例子,如果你是通过自己下棋来不断提升自己的棋艺,那么就是on-policy的,如果是通过看别人下棋来提升自己,那么就是off-policy的

    重要性采样

  • picture 4
  • 对于一个服从概率p分布的变量x, 我们要估计f(x) 的期望。直接想到的是,我们采用一个服从p的随机产生器,直接产生若干个变量x的采样,然后计算他们的函数值f(x),最后求均值就得到结果。但这里有一个问题是,对于每一个给定点x,我们知道其发生的概率,但是我们并不知道p的分布,也就无法构建这个随机数发生器。因此需要转换思路:从一个已知的分布q中进行采样。通过对采样点的概率进行比较,确定这个采样点的重要性。也就是上图所描述的方法。
  • 当然通过这种采样方式的分布p和q不能差距过大,否则,会由于采样的偏离带来谬误。
  • picture 5
  • picture 6
  • 引入上文中说的优势函数可知
  • picture 7
  • picture 8
    • 一套策略参数θ,他与环境交互收集批量数据,然后批量数据关联到 的副本中。他每次都会被更新。
    • 一套策略参数的副本θ’,他是策略参数与环境互动后收集的数据的关联参数,相当于重要性采样中的q分布。
    • 一套评价网络的参数Φ,他是基于收集到的数据,用监督学习的方式来更新对状态的评估。他也是每次都更新。
  • 更新的思路实际上是
    • 0点时:我与环境进行互动,收集了很多数据。然后利用数据更新我的策略,此时我成为1点的我。当我被更新后,理论上,1点的我再次与环境互动,收集数据,然后把我更新到2点,然后这样往复迭代。
    • 但是如果我仍然想继续0点的我收集的数据来进行更新。因为这些数据是0点的我(而不是1点的我)所收集的。所以,我要对这些数据做一些重要性重采样,让这些数据看起来像是1点的我所收集的。当然这里仅仅是看起来像而已,所以我们要对这个“不像”的程度加以更新时的惩罚(KL)。
    • 其中,更新的方式是:我收集到的每个数据序列,对序列中每个(s, a)的优势程度做评估,评估越好的动作,将来就又在s状态时,让a出现的概率加大。这里评估优势程度的方法,可以用数据后面的总折扣奖励来表示。另外,考虑引入基线的Tip,我们就又引入一个评价者小明,让他跟我们一起学习,他只学习每个状态的期望折扣奖励的平均期望。这样,我们评估(s, a)时,我们就可以吧小明对 s 的评估结果就是 s 状态后续能获得的折扣期望,也就是我们的基线。注意哈:优势函数中,前一半是实际数据中的折扣期望,后一半是估计的折扣期望(小明心中认为s应该得到的分数,即小明对s的期望奖励),如果你选取的动作得到的实际奖励比这个小明心中的奖励高,那小明为你打正分,认为可以提高这个动作的出现概率;如果选取的动作的实际得到的奖励比小明心中的期望还低,那小明为这个动作打负分,你应该减小这个动作的出现概率。这样,小明就成为了一个评判官。
    • 当然,作为评判官,小明自身也要提高自己的知识文化水平,也要在数据中不断的学习打分技巧,这就是对Φ的更新了

  • 参考链接

    Ubuntu下开发Linux内核模块

  • Linux内核源码头文件位置/usr/src/linux-headers-$(LINUX_KERNEL)

  • 其中的LINUX_KERNEL是Linux内核版本号,使用uname -r获得

    Makefile

    obj-m := test.o
    CURRENT_PATH := $(shell pwd)
    LINUX_KERNEL := $(shell uname -r)
    LINUX_KERNEL_PATH := /usr/src/linux-headers-$(LINUX_KERNEL)

    all:
    make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
    clean:
    make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean

    更新包含文件的目录

  • 远程端安装C/C++等全套插件(不安装的话没有相应的选项

  • Ctrl+Shift+P打开命令

  • 输入C/C++

  • 图 5

  • 然后在输入框里粘贴地址/usr/src/linux-headers-<uname -r的输出>/include/**/usr/src/linux-headers-<uname -r的输出>/arch/x86/include/

  • picture 4

    • 重启设置之后**可能会消失
  • 然后即可找到printk等函数的定义

    • 图 7

但是还是有报错

  • picture 1

代码文件

#include <linux/init.h>
#include <linux/module.h>

MODULE_LICENSE("Dual BSD/GPL");


static int hello_init(void)
{
printk(KERN_ALERT " Hello World enter\n");
return 0;
}
static void hello_exit(void)
{
printk(KERN_ALERT" Hello World exit\n ");
}

module_init(hello_init);
module_exit(hello_exit);

MODULE_AUTHOR("Song Baohua");
MODULE_DESCRIPTION("A simple Hello World Module");

编译结果

  • 图 3
  • insmod安装模块,rmmod移除模块
    • insmod需要sudo
    • 安装的是.ko文件
    • picture 2
  • 使用dmesg查看系统输出
  • 图 4

  • 参考链接
  • VMware虚拟机网络配置设置为桥接模式,然后使用ifconfig查看IP地址
  • 图 2

Ubuntu端安装SSH

  • sudo apt-get install openssh-server
  • 检查是否安装好
    • ssh -V
  • 查看服务是否启动
    • sudo ps -e |grep ssh
  • 启动SSH
    • sudo service ssh start
  • 修改配置文件
  • SSH服务的配置文件在/etc/ssh/sshd_config下,我们sudo vim /etc/ssh/sshd_config进行修改:
    • 修改一:把配置文件中的”PermitRootLogin without-password“前面加一个”#“号,把它注释掉(也可以直接增加这一句)
    • 修改二:增加一句”PermitRootLogin yes”
  • 保存,退出,重启ssh /etc/init.d/ssh restart

    VSCode端配置

  • 安装remote-ssh插件
  • 新建ssh链接,在命令框中输入ssh 用户名@IP地址 -A
  • 然后保存配置开始链接
  • 图 1

    卡死在创建SSH链接的时候的解决方法

  • picture 1
  • 打开Vscode端的SSH插件设置
  • 找到这一项 勾上对勾
    • picture 2
  • 此外注意不要让ubuntu自动锁屏,否则可能导致连接断开
  • 在此处创建新的控制台picture 3
    • 因为安装SSH的控制台一般无法继续用作其他用途
  • 另外,可以考虑使用rm -r ~/.vscode-server命令删除原先下载的vscode-server(在dpkg搜不到)

解决VMwareTools安装了仍然不能实现虚拟机和主机复制粘贴的问题

  • Ubuntu版本:18.04
  • 先尝试使用VMware提供的安装方法(从插入的CD驱动器中安装包)
  • 失败解决办法
    • 命令行输入sudo apt-get autoremove open-vm-tools
    • 然后使用sudo apt-get install open-vm-tools-desktop
    • 假如安装不上的话就执行sudo apt-get updatesudo apt-get install open-vm-tools-desktop fuse两句命令,但是实际上直接update之后就可以安装了
    • 然后重启虚拟机,尝试拖放和粘贴文字操作已经可行
  • 参考链接

有序表的实现

  • 底层:
    • 红黑树
    • AVL树
    • SB树
    • 跳表
  • 时间复杂度:O(log(N))
  • 红黑树、AVL树、SB树是平衡搜索二叉树

    搜索二叉树的插入和删除

  • 插入直接按照大小分支插入即可
  • 假如没有子节点的节点直接删除即可
  • 假如删除的节点只有一个孩子节点
    • 直接让父节点的指针指向唯一的孩子即可
  • 左右双全:
    • 用左树最右的节点或者是右树最左的节点
    • 这样的节点必然不是两个孩子的节点
    • 先将这个节点的子节点(假如存在)移到这个节点原来的位置
    • 然后将这个节点移到被删除的具有两个孩子的节点的位置

      平衡二叉树

  • 防止因为用户数据输入顺序的原因导致树左右不平衡使得搜索的时间复杂度上升
  • 左树和右树的体量差不多大
  • AVL树在增删结点的时候会从这个节点的父节点开始向上查每个节点的平衡性

从递归到动态规划

  • 只要调用一个递归函数,总有参数不可变和参数可变的部分

  • 不可变的参数对结果没有影响因为都是一样的

  • 分析一个递归函数得到结果依赖下层递归返回什么内容

  • 为什么递归慢?因为会在不同的分支重复遍历相同的情况

    递归到记忆化搜索

    严格表结构的动态规划

  • 解决重复遍历相同情况的问题

  • 利用缓存实现递归函数的可变部分到缓存结果的映射

  • 假如递归函数有k个参数可变,那么缓存的表具有k个维度

  • 缓存表能区分是否计算过这个位置的内容,比如用INT MIN或者-1一类

  • 缓存没命中的话就开始尝试,将尝试的结果存储到表中

  • 时间复杂度O(缓存表的尺寸),本来的复杂度是二叉树的节点数

    计算动态规划表格

  • 动态规划的顺序一定从递归函数的底层情况开始,或者说从递归的终止位置开始,知道不需要计算就直接出答案的位置

  • 从上面的推导得出计算的顺序

  • 利用递归函数的逻辑调用动态规划表格的内容

  • 调用下一级的递归函数更改为从下一级的递归函数的可变参数位置对应的缓存表的位置取出值

  • 也就是将递归调用的过程变成从动态规划表格中取值的过程

  • 小心越界

    斜率优化

  • 假如在递归的过程中出现枚举行为(比如计算一个格子的位置需要循环用到一系列从少到多的格子的信息)

  • 那么可以考虑使用与这个格子临近的格子寻找不需要进行循环就可以直接常数时间内就得到结果的方法

    leetcode 122题 买卖股票的最佳时机II

  • 代码

    class Solution {
    public:
    int maxTemp;
    vector<int> profitCash;
    vector<int> profitHold;
    int maxProfit(vector<int>& prices) {
    profitCash = vector<int>(prices.size(), 0);
    profitHold = vector<int>(prices.size(), 0);
    profitHold[0] = -prices[0];
    for(int i = 1; i < prices.size(); i++)
    {
    profitCash[i] = max(profitHold[i-1]+prices[i], profitCash[i-1]);
    profitHold[i] = max(profitCash[i-1] - prices[i], profitHold[i-1]);
    }
    return profitCash[prices.size()-1];
    }
    };
  • 思路:状态一共两种,此时持有股票或者此时不持有股票,每种有两种操作

  • 持有的话要决定现在卖还是现在不卖,现在卖掉的话更新现在持有现金的最大利润(跟持有现金的前一天比较),否则维持现在持有股票的最大利润

  • 不持有要决定现在买还是现在不买, 现在买的话更新现在持有股票的最大利润(跟持有股票的前一天比较),否则维持现在持有现金的最大利润

    leetcode 123.买卖股票的最佳时机III

  • 与上一题类似,先给出递归的版本(超时)再给出转化为动态规划的版本

  • 分析每一次持仓的时候的动作为减仓和维持不变,每一次没有持仓的时候的操作是加仓和维持不变,这样就可以给出每次状态转换的递归关系,进而通过函数的参数个数(递归函数有剩余交易次数,是否持仓,交易天数三个参数和当前的利润一个结果),给出一个三维数组。

    class Solution {
    public:
    int maxProfit(vector<int>& prices) {
    if(prices.size()<2)return 0;
    return max(trybuyAndSell(prices, 2, false, 0, 1), trybuyAndSell(prices, 1, true, -prices[0], 1));
    }

    int trybuyAndSell(vector<int>& prices, int remain, bool haveStock, int curProfit, int i)
    {
    if(i == prices.size()-1)
    {
    if(haveStock)return curProfit+prices[i];
    else return curProfit;
    }
    if(!haveStock&&remain == 0)
    {
    return curProfit;
    }
    else if(haveStock)
    {
    return max(trybuyAndSell(prices, remain, true, curProfit, i+1), trybuyAndSell(prices, remain, false, curProfit+prices[i], i+1));
    }
    else if(!haveStock)
    {
    return max(trybuyAndSell(prices, remain-1, true, curProfit - prices[i], i+1), trybuyAndSell(prices, remain, false, curProfit, i+1));
    }
    return curProfit;
    }

    int maxProfit(vector<int>& prices)
    {
    int cnt = prices.size()-1;
    if(prices.size()<2)return 0;
    // 第一个维度是剩余次数,第二个是是否持仓,第三个是当前利润
    vector<vector<vector<int>>> mat(3, vector<vector<int>>(2, vector<int>(prices.size(), INT_MIN)));
    mat[1][1][0] = -prices[0];
    mat[2][0][0] = 0;
    for(int i = 1; i<=cnt; i++)
    {
    if(i>1)mat[0][1][i] = max(mat[1][0][i-1] - prices[i], mat[0][1][i-1]);
    if(i>1)mat[0][0][i] = max(mat[0][0][i-1], mat[0][1][i-1]+prices[i]);
    mat[1][1][i] = max(mat[2][0][i-1] - prices[i], mat[1][1][i - 1]);
    mat[1][0][i] = max(i>1?mat[1][0][i-1]:INT_MIN, mat[1][1][i-1]+prices[i]);
    // mat[2][1][i] = max(mat[])
    mat[2][0][i] = mat[2][0][i-1];
    }

    return max(mat[2][0][cnt], max(mat[1][0][cnt], mat[0][0][cnt]));
    }
    };

    leetcode 97.交错字符串

  • 其实不需要根据s3的长度建立很多个数组,因为s1和s2遍历到的位置能直接确定s3遍历到的字符只用建立s1和s2长度为两边的二维数组即可

    class Solution {
    public:
    vector<vector<int>> v;
    bool isInterleave(string s1, string s2, string s3) {
    if(s1.size() == 0)return s2 == s3;
    else if(s2.size() == 0)return s1 == s3;
    v = vector<vector<int>>(s1.size()+1, vector<int>(s2.size()+1, INT_MIN));


    return tryIfPos(s1, s2, s3, 0, 0, 0);
    }


    bool tryIfPos(string&s1, string& s2, string& s3, int i1, int i2, int i3)
    {
    // cout<<i1<<' '<<i2<<' '<<i3<<endl;
    if(v[i1][i2]!=INT_MIN)return v[i1][i2];
    if(i1 == s1.size() && i2 == s2.size())
    {
    if(i3 == s3.size())
    {
    v[i1][i2] = true;
    return true;
    }
    else
    {
    v[i1][i2] = false;
    return false;
    }
    }
    else if(i3 == s3.size())
    {
    v[i1][i2] = false;
    return false;
    }
    bool temp1 = false, temp2 = false;
    if(i1<s1.size()&&s3[i3] == s1[i1])
    {
    if(v[i1+1][i2] == INT_MIN)
    temp1 = tryIfPos(s1, s2, s3, i1+1, i2, i3+1);
    else temp1 = v[i1+1][i2];
    }
    if(i2<s2.size()&&s3[i3] == s2[i2])
    {
    if(v[i1][i2+1] == INT_MIN)
    temp2 = tryIfPos(s1, s2, s3, i1, i2+1, i3+1);
    else temp2 = v[i1][i2+1];
    }
    // cout<<'!';
    if(!(s3[i3] == s1[i1] || s3[i3] == s2[i2]))
    {
    // if(i1<s1.size()&&i2<s2.size()&&i3<s3.size())
    v[i1][i2] = false;
    return false;
    }
    // cout<<'@';
    // if(i1<s1.size()&&i2<s2.size()&&i3<s3.size())
    v[i1][i2] = temp1||temp2;
    return v[i1][i2];
    }
    };
  • 击败100%

    leetcode 44.通配符匹配

  • 将递归转化为动态规划的时候可以采用与递归相同的顺序,比如递归是前面引用后面的,那动态规划也可以写成倒序的方便转换

  • 注意基础位置的条件

    class Solution {
    public:
    bool isMatch(string s, string p) {
    if(s.size() == 0)
    {
    for(int i = 0; i<p.size(); i++)
    {
    if(p[i]!='*')return false;
    }
    return true;
    }
    else if(p.size() == 0)return false;
    vector<vector<bool>> m(s.size(), vector<bool>(p.size(), false));
    int i = p.size()-1;
    if(p[p.size()-1] == s[s.size()-1])
    {
    m[s.size()-1][p.size()-1] = true;
    --i;
    }
    else if(p[p.size()-1] == '?'&&s.size()>0)
    {
    --i;
    m[s.size()-1][p.size()-1] = true;
    }
    else if(p[p.size()-1] == '*')
    {
    for(int i = s.size()-1; i>=0; i--)
    {
    m[i][p.size()-1] = true;
    }
    }
    else return false;
    for(; i>=0; i--)
    {
    for(int si = s.size()-1; si>=0; si--)
    {
    if(s[si] == p[i] || p[i] == '?')
    {
    if(si<s.size()-1&&i<p.size()-1)
    {
    m[si][i] = m[si+1][i+1];
    }
    else if(si<s.size()-1&&i == p.size()-1)
    {
    m[si][i] = false;
    }
    else if(i<p.size()-1&&si == s.size()-1)
    {
    m[si][i] = true;
    for(int k = i+1; k<p.size(); k++)
    {
    if(p[k]!='*')
    {
    m[si][i] = false;
    break;
    }
    }
    }
    else
    {
    m[si][i] = true;
    }
    }
    else if(p[i] == '*')
    {
    if(si<s.size()-1&&i<p.size()-1)
    m[si][i] = m[si+1][i+1]|m[si+1][i]|m[si][i+1];
    else if(si<s.size()-1&&i == p.size()-1)
    {
    m[si][i] = true;
    }
    else if(i<p.size()-1&&si == s.size()-1)
    {
    m[si][i] = m[si][i+1];
    }
    else
    m[si][i] = true;
    }
    else m[si][i] = false;
    }
    }
    return m[0][0];
    }

    bool starUtil(string& s, string& p, int i1, int i2)
    {
    if(s.size() == i1)
    {
    if(i2<p.size())
    {
    for(; i2<p.size(); i2++)
    {
    if(p[i2]!='*')
    {
    return false;
    }
    }
    }
    return true;
    }
    if(p[i2] == '*')
    {
    return starUtil(s, p, i1+1, i2)||starUtil(s, p, i1, i2+1)||starUtil(s, p, i1+1, i2+1);
    }
    else if(s[i1] == p[i2])
    {
    return starUtil(s, p, i1+1, i2+1);
    }
    else if(p[i2] == '?')
    {
    return starUtil(s, p, i1+1, i2+1);
    }
    else return false;
    }
    };

    leetcode 152.乘积最大子数组

  • 注意按照最大和最小分类讨论,因为有正负的问题

    class Solution {
    public:
    int maxProduct(vector<int>& nums) {
    int maxI = INT_MIN;
    vector<vector<int>> m(2, vector<int>(nums.size(), 0));
    m[1][0] = nums[0];
    m[0][0] = nums[0];
    maxI = maxI>=m[0][0]?maxI:m[0][0];
    maxI = maxI>=m[1][0]?maxI:m[1][0];
    for(int i = 1; i<nums.size(); i++)
    {
    m[0][i] = min(nums[i], min(nums[i]*m[0][i-1], nums[i]*m[1][i-1]));
    m[1][i] = max(nums[i], max(nums[i]*m[0][i-1], nums[i]*m[1][i-1]));
    maxI = maxI>=m[0][i]?maxI:m[0][i];
    maxI = maxI>=m[1][i]?maxI:m[1][i];

    }
    return maxI;
    }
    };

leetcode 238.除自身以外数组的乘积

  • 因为不能用除法,所以使用两个数组,一个记录每个位置左侧位置的所有数字乘积,另一个记录右侧,没有元素的话认为是1
    class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> lProduct(nums.size(), 1);
    vector<int> rProduct(nums.size(), 1);
    for(int i = 0; i<nums.size()-1; i++)
    {
    lProduct[i+1] = nums[i]*lProduct[i];
    rProduct[nums.size()-i-2] = nums[nums.size()-1-i]*rProduct[nums.size()-i-1];
    }
    vector<int>ret(nums.size(), 0);
    for(int i = 0; i<nums.size(); i++)
    {
    ret[i] = lProduct[i]*rProduct[i];
    }
    return ret;
    }
    };

    leetcode 322. 零钱兑换

  • 使用最少数目的零钱兑换到指定的面额
  • 注意递归(或者动态规划的循环内外层)的次序是可以改变的,使用零钱作为外层循环和使用剩余需要兑换的额度作为外层循环,该位置的零钱选择作为内层循环要更快一些
  • 要抓到递归的本质是把钱兑换完,而不是把硬币都用一遍
    class Solution {
    public:
    vector<int> m;
    int coinChange(vector<int>& coins, int amount)
    {
    auto cmp = [](int&a, int &b)->bool
    {
    return a>b;
    };
    sort(coins.begin(), coins.end());
    m = vector<int>(amount+1, 10001);

    m[0] = 0;
    for(int i = 0; i<=amount; i++)
    {
    if(m[i]>10000)continue;
    for(auto j = coins.begin(); j!=coins.end()&&*j<=amount-i; j++)
    {
    m[i+*j] = min(m[i+*j], m[i]+1);
    }
    }
    return m[amount]>10000?-1:m[amount];
    }

    };

    leetcode 334. 递增的三元子序列

  • 这题主要是使用两个数组记录每个位置的左侧的最小值和右侧的最大值,找到某个位置的左侧的最小值小于自身和右侧的最大值大于自身的位置即可,此时只需要遍历两次,一次找每个位置左右侧的最值,一次找是否存在符合的点。
    class Solution {
    public:
    bool increasingTriplet(vector<int>& nums) {
    if(nums.size()<3)return false;
    else if(nums.size() == 3)
    {
    if(nums[0]<nums[1]&&nums[1]<nums[2])return true;
    else return false;
    }
    vector<int> lMin(nums.size());
    lMin[0] = nums[0];
    vector<int> rMax(nums.size());
    rMax[nums.size()-1] = nums[nums.size()-1];
    int nSize = nums.size();
    for(int i = 1; i<nSize; i++)
    {
    lMin[i] = min(nums[i], lMin[i-1]);
    rMax[nSize-1-i] = max(rMax[nSize-i], nums[nSize-1-i]);
    }
    for(int i = 1; i<nSize-1; i++)
    {
    if(lMin[i-1]<nums[i]&&rMax[i+1]>nums[i])return true;
    }
    return false;
    }
    };

    leetcode 413. 等差数列划分

  • 寻找的是一个数组中,最小长度为3(可以超过3)的所有子数组的数量之和
  • 比如一个数组跟以他的前一个数字结束的等差数列的公差相同,那么假如前一个数字结束的等差数列的最长长度为k-2(k>=3),那么以这个数字结束的数组的个数就是k+1-2,比如前一个数字结束的数组长度为5,那么以这个数字结束的数组的长度分别是3, 4, 5, 6共4种,正好是5+1-2
    class Solution {
    public:
    int numberOfArithmeticSlices(vector<int>& nums) {
    if(nums.size()<3)return 0;
    else if(nums.size() == 3)
    {
    if(nums[0] - nums[1] == nums[1] - nums[2])return 1;
    else return 0;
    }
    int i = 2;
    while(i<nums.size()&&nums[i] - nums[i-1] != nums[i-1] - nums[i-2])++i;
    if(nums[i] - nums[i-1] != nums[i-1] - nums[i-2])return 0;
    vector<int> diffArr(nums.size(), 0);
    vector<int> lengthArr(nums.size(), 0);
    diffArr[1] = nums[i] - nums[i-1];
    diffArr[2] = nums[i] - nums[i-1];
    lengthArr[2] = 1;
    int cnt = 1;
    i+=1;
    for(;i<nums.size(); i++)
    {
    int temp = nums[i] - nums[i-1];
    diffArr[i] = temp;
    if(temp == diffArr[i-1])
    {
    lengthArr[i] = lengthArr[i-1]+1;
    cnt+=lengthArr[i];
    }

    }
    return cnt;
    }
    };

    leetcode 300. 最长递增子序列

  • 设置一个记录数组,记录以每个位置结尾的最长递增数组的长度
  • 此题不能改变原来数组的排序,在原来数组中寻找一个递增的子序列(不需要连续)
  • 遍历的方式是指定当前递增序列的结尾数字,在当前位置之前寻找一个比他小但是以这个位置结尾的数组最长的位置,将以当前位置结尾的递增数组的长度修改为前面选定的位置的递增数组的长度+1
    class Solution {
    public:
    int lengthOfLIS(vector<int>& nums) {
    // int maxLen = 0;
    int n = nums.size();
    vector<int> lenArr(n, 1);
    vector<int> ret;
    int maxEnd = 0;
    int maxLen = 1;
    for(int i = 1; i<n; i++)
    {
    for(int j = 0; j<i; j++)
    {
    if(nums[j]<nums[i])
    {
    lenArr[i] = max(lenArr[i], lenArr[j]+1);
    if(lenArr[i]>maxLen)
    {
    maxLen = lenArr[i];
    maxEnd = i;
    }
    }
    }
    }
    return maxLen;

    }
    };

    leetcode 368.最大整除子集

  • 此题是在一个数组中寻找一个子数组(不需要连续,而且可以改变原来的数组的顺序),数组中的每个元素都能被上一个元素整除,寻找总长度最长的子数组
  • 给出一个与原来的数组大小相同的长度记录数组(以当前位置作为最后一个元素的整除数组的最大长度)
  • 首先将数组从小到大排序
  • 然后在0位置给出当前位置的最长整除数组为1
  • 然后以第i个元素为末尾,遍历比这个元素小的所有元素,寻找能整除第i个元素而且以该数字结尾的数组最长的位置,将i位置的以该位置结束的数组的最大长度设置为前面找到的最长数组的长度+1
  • 因为无法确定每个位置的数字是否需要,所以要以n^2的时间复杂度遍历
  • 回溯寻找这个最长的数组的时候,从当前最长数组的结尾元素的前一个元素开始,假如这个元素能整除当前的结尾元素,并且以这个元素结尾的数组的长度恰好是最大长度-1,那么这个元素就是待求数组当前结尾元素的前一个元素,将其替换为当前待求的结尾元素,将最大长度-1,重复上述过程。
    class Solution {
    public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
    if(nums.size()<2)return vector<int>(nums);
    sort(nums.begin(), nums.end());
    int maxLen = 0, n = nums.size();
    int maxEnd = 0;
    vector<int> lenArr(n, 0);
    vector<int>ret;
    vector<vector<int>> m(n);
    for(int i = 1; i<n; i++)
    {
    for(int j = 0; j<i; j++)
    {
    if(nums[i]%nums[j] == 0)
    {
    lenArr[i] = max(lenArr[i], lenArr[j]+1);
    if(maxLen<lenArr[i])
    {
    maxLen = lenArr[i];
    maxEnd = i;
    }
    }
    }
    }
    int temp = nums[maxEnd];
    ret.push_back(nums[maxEnd--]);
    while(maxEnd>=0)
    {
    if(temp%nums[maxEnd] == 0&&lenArr[maxEnd] == maxLen-1)
    {
    ret.insert(ret.begin(), nums[maxEnd]);
    temp = nums[maxEnd];
    --maxEnd;
    --maxLen;
    }
    else
    {
    --maxEnd;
    }
    }
    return ret;
    }
    };

    牛客 HJ77 火车进站

  • 链接
  • 此题的主要回溯逻辑就是是否弹出栈中元素,可以弹出后再插入当前元素,或者不弹出直接插入
  • 注意防止重复,一层递归只能插入一次
    #include <iostream>
    #include <mutex>
    #include <vector>
    #include <stack>
    #include <algorithm>
    using namespace std;
    vector<vector<int>> ans;
    void traversal(vector<int>& v, stack<int> s, int beg, vector<int>& res)
    {
    if(beg == v.size())
    {
    stack<int> ts;
    int toPop = s.size();
    while(s.size())
    {
    res.push_back(s.top());
    ts.push(s.top());
    s.pop();

    }
    ans.push_back(res);
    for(int i = 0; i< toPop; ++i)
    {
    res.pop_back();
    }
    while(ts.size())
    {
    s.push(ts.top());
    ts.pop();
    }
    return ;
    }
    if(s.size())
    {
    int tmp = s.top();
    res.push_back(tmp);
    s.pop();
    traversal(v, s, beg, res);
    s.push(tmp);
    res.pop_back();
    }
    s.push(v[beg]);
    traversal(v, s, beg+1, res);
    s.pop();
    }

    int main() {
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i<n; ++i)
    {
    cin>>v[i];
    }
    stack<int> s;
    vector<int> a;

    traversal(v, s, 0, a);
    sort(ans.begin(), ans.end(), [](vector<int>&a, vector<int>&b) -> bool
    {
    for(int i = 0; i<a.size(); ++i)
    {
    if(a[i]!=b[i])return a[i]<b[i];
    }
    return false;
    });
    for(auto & r : ans)
    {
    for(auto i : r)
    {
    cout<<i<<' ';
    }
    cout<<endl;
    }

    }
    // 64 位输出请用 printf("%lld")

用位运算实现两个数字比较大小

  • 图 10
  • 图 11
  • 图 12
  • 具体操作为获得a, b和a与b的差值的符号,然后利用difSab和sameSab这两个互斥(一个为1的时候另一个必然是0)的变量实现if和else的功能
  • 利用加号左右两侧互斥的变量实现if else 的功能

    取出数字最右侧位置的1

    num & (~num + 1)

    位运算加法实现

  • 图 2
  • a和b异或,得到无进位加法结果
  • a和b与的结果左移一位,得到进位的位置,二者相加
  • 然后再把进位和无进位加法的结果求异或、与,左移一位,然后相加,重复上述步骤,直到没有进位为止

    位运算减法实现

  • 加一个数的相反数
  • 相反数等于一个数字取反再+1

    位运算乘法

  • 假如一个数字二进制第k位是1,那么就将原始数字向左移k位,从k=0开始直到最大位,累加即可
  • 图 1

    位运算除法

  • a/b
  • b尽可能左移,但是不能超过a,假设移动了k1位,得到b’
  • 那么除法的第k位一定是1
  • 计算此时a-b’
  • 然后再次将b左移,但是不超过上次a-b’的结果,移动了k2位
  • 除法结果的第k2位也是1
  • 循环往复
  • 实际操作是a右移k位,判断是否比b大,原因是b左移可能溢出熬制不安全,符号位改变等等
  • 图 3
  • 最后假如有余数的话丢弃(就是b不移位也不能减)