576 出界的路径数

m*n表格(1x1~50x50)中一个位置在给定maxMove(0~50)的情况下到达边框外的路径数量和

有三个参数，起始点的横纵坐标，移动次数，递推关系在于相邻格子的路径数和maxMove限制。比较难想的一点是以移动次数做递推，由初始化保证是从start点出发，讲到达超出边界的路径数求和

剩下就是动态规划标准路数：

设 $\text{dp}[k][i][j] := 移动 k 次后到达坐标(i,j)的路径数$

init: $\text{dp}[0][start_i][start_j]=1$ ； $\text{dp}[0][other_i][other_j]=0$

recurrence:

1
2
3
4

if around in grad:
    dp[k+1][around_i][around_j]+=dp[k][i][j]
else outside:
    ans+=dp[k][i][j]

time:

$O(n)=O(maxMove*m*n)$

526 优美的排列

n(1~15)个数的排列组合，第i位数和下标i有整除关系。

挺直白的一道回溯题。解题通常是逐个尝试，不行回退。一般要维护一个visit数组记录当前过程的回溯情况。回溯走到尽头时把记录数+1。

这道题为了优化回溯效率，还可以预处理每个索引可以存在的数字。

dfs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

backtrace = func(index int) {
    if end:
        ans++
        return
    for _,val := range choice[index]:
        if  not visit[val]:
            visit[val] = true
            backtrace(index + 1)
            visit[val] = false
}

528 按权重随机选择

前缀和+二分查找

设数组 w 的权重之和为 $$\textit{total}$$。根据题目的要求，我们可以看成将 $$[1, \textit{total}]$$ 范围内的所有整数分成 n 个部分（其中 n 是数组 w 的长度）

PS：对应操作系统小知识点：彩票调度 可是说是这个题目的应用场景吧

502 IPO

纯利润 profits[i] ，启动资本 capital[i]，初始资本 w，选k个最大化净利润

如果没有k个限制，直接按capital[i]从小到大排，不停加profits，直到加不了。而根据现在的题目限制，可以贪心的选取目前持有资本下获得利润最多的项目i，形式化的写法可以用： $$ w \text{+=} profits[i] \text{【capital[i]<w & max(profits[i])】} $$ capital[i]和profits[i] 构成元组，以capital[i]为指标排序，满足小于w的情况下遍历capital找最大的profits[i] ，这边可以用堆做数据结构优化，存入元组的profits[i] 项，然后取出堆顶元素，重复k次即可。

PS：对应操作系统小知识点：银行家算法

470 用 Rand7() 实现 Rand10()

概率题：

1.如何利用一个小范围随机数，得到一个大范围等概率随机数？

采用随机数的 k 进制，对于 randN，采用 N 进制，即：(randN - 1) * N + randN 得到了一个 N*N 范围的等概率随机数，如果还不够大，可以继续在 randN 或生成的 randN*N 上使用这个。

2.如何利用一个小范围随机数，得到一个确定范围的等概率随机数？

先采用随机数的 k 进制，得到一个不小于确定范围的随机数 randK，然后对超过确定范围数进行拒绝即可。 注意，如果 K 比确定范围大太多，拒绝策略效率可能就会比较低（经常生成要拒绝的随机数），此时可以把要拒绝的随机数看成一个新的 randM，然后针对这个 randM 再思考怎么用这三个方法也得到确定范围的随机数

3.补充技能

对于随机数 randN，只要 K 是 N 的约数（或者说 N 是 K 的整数倍），都可以通过 randN 一步得到 randK：randK = (randN % K) + 1;