【状态机动态规划 组合数学】100298. 到达第 K 级台阶的方案数_动态规划 方案数

本文涉及知识点

组合数学 状态机动态规划
动态规划汇总
组合数学汇总

LeetCode 100298. 到达第 K 级台阶的方案数

给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
虎老师有一个整数 jump ，一开始值为 0 。虎老师从台阶 1 开始，虎老师可以使用 任意 次操作，目标是到达第 k 级台阶。假设虎老师位于台阶 i ，一次 操作 中，虎老师可以：
向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
请你返回虎老师到达台阶 k 处的总方案数。
注意 ，虎老师可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
虎老师从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
虎老师从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
执行第一种操作，从台阶 1 向下走到台阶 0 。
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
虎老师从台阶 1 开始，已经到达台阶 1 。
虎老师从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
虎老师从台阶 1 开始。
执行第二种操作，向上走 20 级台阶到台阶 2 。
执行第一种操作，向下走 1 级台阶到台阶 1 。
虎老师从台阶 1 开始。
执行第一种操作，从台阶 1 向下走到台阶 0 。
执行第二种操作，向上走 20 级台阶到台阶 1 。
执行第一种操作，向下走 1 级台阶到台阶 0 。
执行第二种操作，向上走 21 级台阶到台阶 2 。
执行第一种操作，向下走 1 级台阶到台阶 1 。
提示：
0 <= k <= 10⁹

枚举jump，计算back

我们称第一种方式为后退，第二种方式为跳跃。跳跃jump次移动的距离为 (1 << jump) -1 ，jump为0也符合。
如果后退了back次，则最终位置为： 1 + (1 << jump) -1 -back 如果能移到k，则 back = 1 + (1 << jump) -1 - k 。
如果back 小于0或大于jump+1则非法。 跳跃前，可以后退一次。每次跳跃后，可以后退一次。
如果back 为0，则方案数+1。否则要动态规划。
jump只需要枚举到40（可能更少），因为： 1 + (1LL << 40)-1 -back 远远大于k

动态规划

枚举jump，计算出back后，通过动态规划讨论方案数。

动态规划的状态表示

pre[j] 表示跳跃i次后，后退j次合法方案的数量。
dp[j] 及时pre[j+1]。
空间复杂度： 如果使用滚动向量，则空间复杂度为O(back)；不使用滚动向量，空间复杂度为O(jump$\times$bakc)。

动态规划的转移方程

{ d p [ j ] + = p r e [ j ] 不后退 d p [ j + 1 ] + = p r e [ j ] 后退 ( j + 1 < = b a c k ) 且当前位置大于 0

$$\begin{cases} dp[j] += pre[j] && 不后退 && \\ dp[j+1] += pre[j] && 后退 && (j+1 <= back) 且当前位置大于0 \\ \end{cases}$$ {dp[j]+=pre[j]dp[j+1]+=pre[j]​​不后退后退​​(j+1<=back)且当前位置大于0​
通过前置状态更新后置状态。每个状态更新的时间复杂度是：O(1)，故总时间复杂度是：O(jump$\times$bakc)

动态规划的初始值

pre[0]=pre[1] = 1 ，其它全为0。

动态规划的填表顺序

i = 1 To jump

动态规划的返回值

pre.back

动态规划的代码

核心代码

class Solution {
public:
	int waysToReachStair(int k) {
		int iRet = 0;	
		for (int jump = 0; jump <= 40; jump++) {
			const long long hasJump = (1LL << jump) - 1;	
			const long long back = 1 + hasJump - k;
			if ((back < 0) || (back > 1 + jump)) { continue; }
			if (0 == back) { iRet++; continue; }
			vector<int> pre(back + 1);
			pre[0] = 1;
			pre[1] = 1;
			for (int i = 1; i <= jump; i++) {				 
				vector<int> dp(back + 1);
				for (int j = 0; j < pre.size(); j++) {
					const long long llPosAfterJump = 1 + (1LL << i) - 1 - j;
					dp[j] += pre[j]; //不后退
					if ((llPosAfterJump > 0)&&(j+1 < pre.size())) {
						dp[j + 1] += pre[j];
					}
				}
				dp.swap(pre);
			}
			iRet += pre.back();
		}
		return iRet;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

测试用例

int main()
{	
	int k;
	{
		Solution slu;
		vector<int> ans = {2,4,4,3,2,4,6,4,1,0};
		for (int k = 0; k < 10; k++)
		{
			auto res = slu.waysToReachStair(k);
			Assert(res, ans[k]);
		}
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13

组合数学

周赛时不用组合数学的原因，是担心后退后位置为负而非法。实际上这种可能不存在。
共有jump+1个后退位，每个后退位之前，都有个大于等于1的数。就算全部后退位都后退，也不会变成负数。
共有：C${}_{jump+1}^{back}$

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。