DAY 58 动态规划

**DAY58: 动态规划**

动态规划（Dynamic Programming）是一种常见的算法技巧，用于解决复杂的问题。它通过分解问题，找到子问题之间的重叠，并缓存已计算过的结果来提高效率。

###什么是动态规划？

动态规划是一种顶-down 的方法，它首先解决最小的子问题，然后逐渐合并这些子问题，以求出原来的问题的解。这种方法尤其适用于有重叠子问题的递归问题。

### 动态规划的步骤1. **分解问题**: 将原来的问题分解成多个子问题，每个子问题都可以独立解决。
2. **找到子问题之间的重叠**: 确定哪些子问题有重叠，这样我们就可以避免重复计算。
3. **缓存已计算过的结果**: 使用一个表格或数组来存储已经计算过的子问题的答案，以便下次遇到相同的问题时直接使用。

### 动态规划的优点1. **提高效率**: 动态规划可以避免重复计算，从而显著提高算法的效率。
2. **减少内存占用**: 只需要缓存已经计算过的结果，而不是所有可能的子问题，这样就能节省大量的内存。

### 动态规划的缺点1. **增加了空间复杂度**: 需要额外的空间来存储缓存的结果。
2. **需要仔细分析问题**: 才能确定哪些子问题有重叠，如何缓存结果。

### 实例：斐波那契数列斐波那契数列是一个经典的动态规划问题。斐波那契数列的第 n 个数字是前两个数字之和。

def fibonacci(n):
 # 创建一个表格来缓存结果 fib = [0] * (n +1)
 # 初始化第一行 fib[0] =0 fib[1] =1 # 计算斐波那契数列 for i in range(2, n +1):
 fib[i] = fib[i -1] + fib[i -2]
 return fib[n]

# 测试函数print(fibonacci(10)) # 输出:55

def longest_ascending_subsequence(arr):
 # 创建一个表格来缓存结果 dp = [1] * len(arr)
 # 初始化第一行 for i in range(1, len(arr)):
 for j in range(i):
 if arr[i] > arr[j]:
 dp[i] = max(dp[i], dp[j] +1)
 return max(dp)

# 测试函数arr = [10,22,9,33,21,50,41,60]
print(longest_ascending_subsequence(arr)) # 输出:6