Acwing学习笔记

Acwing

状态的划分

https://www.bilibili.com/video/av67759585/

矩阵路径问题 最低通行费问题

dp数组的长度 什么时候定义为len(n)，什么时候定义为len(n)+1?

当dp[0]与迭代对象第0位元素的状态值的含义一致时，用len(n)来定义dp数组的长度，在斐波那契数列问题里这种定义方式较多；
如果需要用dp[0]来表示一种初始状态，与迭代对象中的元素含义无关，则需要用到len(n)+1，来定义dp数组的长度。在背包问题里这种定义方式较多；

方格取数

两条路线同时走，同一时刻两条路线走过的总步数相等，都为k
同一时刻，路线1所在横坐标为i1，纵坐标为j1=k-i1；路线2所在横坐标为i2，纵坐标为j2=k-i2
如果i1==i2，则两条路线在(i1,k-i1)点处重合，只能加一个w
如果i1!=i2，则两条路线在(i1,k-i1)点处不重合，加两个w
分四种情况线路一下移、线路一右移，线路二下移、线路二右移
dp[k][i1][j1]表示总步数为k，当前坐标为(i1,j1)时，途径的路线上取得的整数和的最大值

快速排序

主要思想：分治法
1、确定分界点x
2、调整区间，使得分界点左边的都是小于等于x的，右边的都是大于等于x的
3、递归处理左右两段

归并排序

两个有序序列，双路归并、合二为一