1 动态规划的递归写法和递推写法

E407: 斐波拉契数列II

https://sunnywhy.com/sfbj/11/1/407

给定正整数n，求斐波那契数列的第n项F(n)。

令F(n)表示斐波那契数列的第n项，它的定义是：

当 n = 1 时，F(n) = 1；
当 n = 2 时，F(n) = 1；
当 n > 2 时，F(n) = F(n-1) + F(n-2)。

大数据版：斐波拉契数列-大数据版

输入描述

一个正整数n（ $1 \leq n \leq 10^{4}$ ）。

输出描述

斐波那契数列的第n项F(n)。

由于结果可能很大，因此将结果对10007取模后输出。

样例1

输入

输出

复制

样例2

输入

输出

样例3

输入

输出

python

MOD = 10007


def f(n):
    if n in {1, 2}:
        return 1

    pre1 = 1
    pre2 = 1
    current = 0
    for i in range(3, n + 1):
        current = (pre1 + pre2) % MOD
        pre2 = pre1
        pre1 = current

    return current


num = int(input())
print(f(num))

M893: 斐波拉契数列-大数据版

https://sunnywhy.com/problem/893

斐波那契数列是一种经典的数列，定义如下：

当 n = 1 时，F(n) = 1；
当 n = 2 时，F(n) = 1；
当 n > 2 时，F(n) = F(n-1) + F(n-2)。

给定一个正整数 n，请你计算斐波那契数列的第 n 项 F(n)。由于结果可能非常大，请输出对 10^9 + 7 取模后的结果。

输入描述

输入包含一个正整数 n，表示需要求解的斐波那契数列项的编号。（ $1 \leq n \leq 10^{18}$ ）

输出描述

输出斐波那契数列的第 n 项对 10^9 + 7 取模后的结果。

样例1

输入

输出

解释

第项斐波那契数为 1，对 10^9 + 7 取模后的结果为 1。

样例2

输入

1000000000000000000

输出

209783453

解释

第项斐波那契数对 10^9 + 7 取模后的结果为 209783453。

要计算斐波那契数列的第 ( n ) 项并对 ( 10^9 + 7 ) 取模，可以使用矩阵快速幂的方法。以下是详细的步骤和代码实现：

定义矩阵乘法函数 matrix_mult。
定义矩阵快速幂函数 matrix_pow。
使用矩阵快速幂计算斐波那契数列的第 ( n ) 项。

python

MOD = 10 ** 9 + 7

def matrix_mult(A, B):
    return [
        [(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD],
        [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD]
    ]

def matrix_pow(matrix, n):
    result = [[1, 0], [0, 1]]  # Identity matrix
    base = matrix

    while n > 0:
        if n % 2 == 1:
            result = matrix_mult(result, base)
        base = matrix_mult(base, base)
        n //= 2

    return result

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    F = [[1, 1], [1, 0]]
    result = matrix_pow(F, n - 1)
    return result[0][0]

num = int(input())
print(fibonacci(num))

矩阵快速幂是一种高效的算法，用于计算一个方阵（n x n 矩阵）的高次幂。这个方法基于普通整数快速幂的思想，通过将问题分解为更小规模的问题来加速计算过程。它通常用于解决线性递推关系（如斐波那契数列）的大指数项计算、图论中的路径计数等问题。

基本思想

快速幂：对于整数 a 和非负整数 b，计算 $a^{b}$ 可以通过不断平方的方式来减少乘法次数。例如，计算 $a^{13}$ 可以表示为( $a \times (a^{2})^{6}$ 。
矩阵乘法：两个矩阵 A 和 B 相乘的结果是另一个矩阵 C，其中C[i][j]等于A的第i行与B的第j列对应元素乘积之和。

算法步骤

给定一个 $n \times n$ 的矩阵M和一个正整数k，要计算 $M^{k}$ ：

如果k=0，则结果是单位矩阵（对角线全为1，其他位置为0）。
如果k>0，将k转换为其二进制形式。
初始化结果矩阵R为单位矩阵。
对于k的每一位，如果该位是1，则将当前R与M相乘，并更新R；无论该位是什么，都将M自乘一次。
重复步骤4直到处理完k的所有位。

代码示例

这里提供一个简单的Python实现：

python

import numpy as np

def matrix_power(matrix, power):
    # 获取矩阵的维度
    n = len(matrix)
    
    # 结果矩阵初始化为单位矩阵
    result = np.eye(n, dtype=int)
    
    while power > 0:
        if power % 2 == 1:  # 当前位是1
            result = np.dot(result, matrix)
        # 矩阵自乘
        matrix = np.dot(matrix, matrix)
        # 右移一位
        power //= 2
    
    return result

# 示例
M = np.array([[1, 1], [1, 0]], dtype=int)  # 斐波那契数列的转移矩阵
k = 10  # 计算M的10次幂
print(matrix_power(M, k))

在这个例子中，matrix_power函数接收一个方阵matrix和一个整数power作为输入，并返回matrix的power次幂。使用NumPy库简化了矩阵运算的实现。

应用

斐波那契数列：利用特定的转移矩阵，可以非常高效地计算大索引处的斐波那契数。
图论：在有向图中， $A^{n}$ 中的 $A_{i j}$ 给出了从节点i到节点j长度恰好为(n)的路径数量。
动态规划：某些动态规划问题可以通过构建适当的转移矩阵并求其幂来优化解决方案。

这种方法极大地减少了所需的时间复杂度，特别是当指数很大时。

方法二：用「斐波那契数列快速倍增法 (fast doubling)」直接 O(log n) 求 F(n)

✅ 最快 & 最简洁的非矩阵做法：快速倍增法（Fast Doubling）

递推公式：

$F (2 k) = F (k) \cdot [2 F (k + 1) - F (k)]$ $F (2 k + 1) = F (k)^{2} + F (k + 1)^{2}$

一次递归返回两个值：F(n) 和 F(n+1) 时间复杂度：O(log n) 空间复杂度：O(log n)（递归深度）

python

MOD = 10**9 + 7

def fib(n):
    if n == 0:
        return (0, 1)
    a, b = fib(n >> 1)
    c = (a * ((b * 2 - a) % MOD)) % MOD
    d = (a * a + b * b) % MOD
    if n & 1:
        return (d, (c + d) % MOD)
    else:
        return (c, d)

n = int(input())
print(fib(n)[0])

🔍 代码解释（简明）

fib(n) 返回 (F(n), F(n+1))
通过 n 的二分（位移）不断递归
用倍增公式构造 F(2k)、F(2k+1)
最终得到 F(n)

E408: 数塔II 简单

dp, https://sunnywhy.com/sfbj/11/1/408

数塔就是由一堆数字组成的塔状结构，其中第一行1个数，第二行2个数，第三行3个数，依此类推。每个数都与下一层的左下与右下两个数相连接。这样从塔顶到塔底就可以有很多条路径可以走，现在需要求路径上的数字之和的最大值。

例如在上图中，5->8->12->10与5->3->16->11这两条路径上的数字之和都是35，是所有路径中的最大值。

输入描述

第一行一个正整数n（1 <= n <= 100），表示数塔的层数。

接下来行为数塔从上到下的每一层，其中第层有个正整数，每个数都不超过1000。

输出描述

从塔顶到塔底的所有路径中路径上数字之和的最大值。

样例1

输入

输出

解释

5->8->12->10与5->3->16->11这两条路径上的数字之和都是35，是所有路径中的最大值。

自底向上

python

n = int(input())
triangle = []
for i in range(n):
    row = list(map(int, input().split()))
    triangle.append(row)

# 自底向上 DP
for i in range(n - 2, -1, -1):  # 从倒数第二层开始往上
    for j in range(len(triangle[i])):
        triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])

print(triangle[0][0])

E409: 上楼II 简单

https://sunnywhy.com/sfbj/11/1/409

我打算走楼梯上楼，共有级台阶。

我身轻如燕，所以每次都可以选择上一级台阶或者两级台阶。

问有多少种上楼的方式。

例如当时，共有三种方式上楼：

一级 => 一级 => 一级；
一级 => 二级；
二级 => 一级。

输入描述

一个正整数（），表示台阶级数。

输出描述

一个整数，表示上楼的方案数。

由于结果可能很大，因此将结果对取模后输出。

样例1

输入

输出

解释

只有一种方案：直接一级

样例2

输入

输出

解释

有两种方案：

一级 => 一级
二级

样例3

输入

输出

解释

有三种方案：

一级 => 一级 => 一级
一级 => 二级
二级 => 一级

python

def climb_stairs(n):
    MOD = 10**4 + 7  
    if n == 1:
        return 1
    if n == 2:
        return 2
        
    # 初始化前两个状态
    a, b = 1, 2  # f(1)=1, f(2)=2（通过迭代自然推导）
    for _ in range(3, n+1):
        a, b = b, (a + b) % MOD
    return b

# 读取输入并输出
n = int(input())
print(climb_stairs(n))

1 动态规划的递归写法和递推写法 ​

E407: 斐波拉契数列II ​

M893: 斐波拉契数列-大数据版 ​

E408: 数塔II 简单 ​

E409: 上楼II 简单 ​

1 动态规划的递归写法和递推写法

E407: 斐波拉契数列II

M893: 斐波拉契数列-大数据版

E408: 数塔II 简单

E409: 上楼II 简单