find-number-of-ways-to-reach-the-k-th-stair

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a non-negative integer <code>k</code>. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.

Alice has an integer <code>jump</code>, with an initial value of 0. She starts on stair 1 and wants to reach stair <code>k</code> using any number of operations. If she is on stair <code>i</code>, in one operation she can:

<ul>
	<li>Go down to stair <code>i - 1</code>. This operation cannot be used consecutively or on stair 0.</li>
	<li>Go up to stair <code>i + 2jump</code>. And then, <code>jump</code> becomes <code>jump + 1</code>.</li>
</ul>

Return the total number of ways Alice can reach stair <code>k</code>.

Note that it is possible that Alice reaches the stair <code>k</code>, and performs some operations to reach the stair <code>k</code> again.

&nbsp;
Example 1:

<div class="example-block">
Input: k = 0

Output: 2

Explanation:

The 2 possible ways of reaching stair 0 are:

<ul>
	<li>Alice starts at stair 1.
	<ul>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
	</ul>
	</li>
	<li>Alice starts at stair 1.
	<ul>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
		<li>Using an operation of the second type, she goes up 20 stairs to reach stair 1.</li>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
	</ul>
	</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: k = 1

Output: 4

Explanation:

The 4 possible ways of reaching stair 1 are:

<ul>
	<li>Alice starts at stair 1. Alice is at stair 1.</li>
	<li>Alice starts at stair 1.
	<ul>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
		<li>Using an operation of the second type, she goes up 20 stairs to reach stair 1.</li>
	</ul>
	</li>
	<li>Alice starts at stair 1.
	<ul>
		<li>Using an operation of the second type, she goes up 20 stairs to reach stair 2.</li>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 1.</li>
	</ul>
	</li>
	<li>Alice starts at stair 1.
	<ul>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
		<li>Using an operation of the second type, she goes up 20 stairs to reach stair 1.</li>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 0.</li>
		<li>Using an operation of the second type, she goes up 21 stairs to reach stair 2.</li>
		<li>Using an operation of the first type, she goes down 1 stair to reach stair 1.</li>
	</ul>
	</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= k &lt;= 109</code></li>
</ul>

waysToReachStair

Find Number of Ways to Reach the K-th Stair

Climbing Stairs

climbing-stairs

爬楼梯

Min Cost Climbing Stairs

min-cost-climbing-stairs

使用最小花费爬楼梯

Bit Manipulation

Memoization

Math

Dynamic Programming

Combinatorics

给你有一个 非负&nbsp;整数&nbsp;<code>k</code>&nbsp;。有一个无限长度的台阶，最低&nbsp;一层编号为 0 。

Alice&nbsp;有一个整数&nbsp;<code>jump</code>&nbsp;，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意&nbsp;次操作，目标是到达第&nbsp;<code>k</code> 级台阶。假设 Alice 位于台阶 <code>i</code> ，一次 操作 中，Alice 可以：

<ul>
	<li>向下走一级到&nbsp;<code>i - 1</code>&nbsp;，但该操作&nbsp;不能&nbsp;连续使用，如果在台阶第 0 级也不能使用。</li>
	<li>向上走到台阶&nbsp;<code>i + 2jump</code>&nbsp;处，然后&nbsp;<code>jump</code>&nbsp;变为&nbsp;<code>jump + 1</code>&nbsp;。</li>
</ul>

请你返回 Alice 到达台阶 <code>k</code>&nbsp;处的总方案数。

注意，Alice 可能到达台阶 <code>k</code>&nbsp;处后，通过一些操作重新回到台阶 <code>k</code>&nbsp;处，这视为不同的方案。

&nbsp;

示例 1：

<div class="example-block">
输入：k = 0

输出：2

解释：

2 种到达台阶 0 的方案为：

<ul>
	<li>Alice&nbsp;从台阶&nbsp;1 开始。
	<ul>
		<li>执行第一种操作，从台阶 1 向下走到台阶 0 。</li>
	</ul>
	</li>
	<li>Alice&nbsp;从台阶 1 开始。
	<ul>
		<li>执行第一种操作，从台阶 1 向下走到台阶 0 。</li>
		<li>执行第二种操作，向上走 20&nbsp;级台阶到台阶 1 。</li>
		<li>执行第一种操作，从台阶 1 向下走到台阶 0 。</li>
	</ul>
	</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入：k = 1

输出：4

解释：

4 种到达台阶 1 的方案为：

<ul>
	<li>Alice&nbsp;从台阶 1 开始，已经到达台阶 1 。</li>
	<li>Alice&nbsp;从台阶 1 开始。
	<ul>
		<li>执行第一种操作，从台阶 1 向下走到台阶 0 。</li>
		<li>执行第二种操作，向上走 20&nbsp;级台阶到台阶 1 。</li>
	</ul>
	</li>
	<li>Alice&nbsp;从台阶 1 开始。
	<ul>
		<li>执行第二种操作，向上走 20&nbsp;级台阶到台阶 2 。</li>
		<li>执行第一种操作，向下走 1 级台阶到台阶 1 。</li>
	</ul>
	</li>
	<li>Alice&nbsp;从台阶 1 开始。
	<ul>
		<li>执行第一种操作，从台阶 1 向下走到台阶 0 。</li>
		<li>执行第二种操作，向上走&nbsp;20&nbsp;级台阶到台阶 1 。</li>
		<li>执行第一种操作，向下走 1 级台阶到台阶 0 。</li>
		<li>执行第二种操作，向上走 21&nbsp;级台阶到台阶 2 。</li>
		<li>执行第一种操作，向下走&nbsp;1 级台阶到台阶 1 。</li>
	</ul>
	</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= k &lt;= 109</code></li>
</ul>