动态规划数组python

### 动态规划与数组的应用

动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。当一个问题可以被分割成几个相似的小问题时，通常可以用动态规划来解决。

#### 使用Python实现斐波那契数列作为入门例子

斐波那契数列是一个经典的动态规划案例：

def fibonacci(n):
    if n <= 0:
        return "Input should be positive integer."
    elif n == 1 or n == 2:
        return 1
    
    fib = [0] * (n + 1)
    fib[1], fib[2] = 1, 1
    
    for i in range(3, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

print(fibonacci(10))

此代码展示了如何利用列表存储中间计算结果以避免重复运算，从而提高效率[^1].

#### 数组中的最长递增子序列(Longest Increasing Subsequence)

这个问题旨在找到给定整数数组中最长严格增加的子序列长度:

from bisect import bisect_left

def length_of_LIS(nums):
    dp = []
    for num in nums:
        pos = bisect_left(dp, num)
        if pos == len(dp):
            dp.append(num)
        else:
            dp[pos] = num
    return len(dp)

nums_example = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_LIS(nums_example))  

上述程序采用二分查找优化了时间复杂度至O(N log N)，其中N代表输入数组大小.

#### 零钱兑换(Coin Change Problem)

该问题是关于找出能够凑齐特定金额所需的最少硬币数量:

import math

def coinChange(coins, amount):
    dp = [math.inf] * (amount + 1)
    dp[0] = 0
    
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
                
    return dp[amount] if dp[amount] != math.inf else -1 

coins_example = [1, 2, 5]
amount_example = 11
print(coinChange(coins_example, amount_example))

这段脚本实现了自底向上的迭代方法来解决问题，并初始化了一个无限大值填充的结果表`dp[]`用于记录最小硬币数目.