动态规划

动态规划问题的一般形式：求最值、求最长递增子序列、最小编辑距离

动态规划问题一定具备最优子结构

重叠子问题、最优子结构、状态转移方程

定义状态转移方程：明确[状态]-->定义dp数组/函数的含义-->明确[选择]-->明确base case

1 def fib(n):
2     if n == 1 or n == 2:
3         return 1
4     return fib(n-1) + fib(n-2)

 # 带备忘录的递归解法-->自顶向下的动态规划
 1 def fib(n):
 2     memo = [0 for i in range(n+1)]
 3     return helper(memo, n)
 4 
 5 def helper(memo, n):
 6     if n==1 or n == 2:
 7         return 1
 8     if memo[n] != 0:
 9         return memo[n]
10     memo[n] = helper(memo, n-1) + helper(memo, n-2)
11     return memo[n]

1 # 动态规划解法-->自底向上的迭代解法
2 def fib(n):
3     dp = [0 for i in range(n+1)]
4     dp[1] = dp[2] = 1
5     for i in range(3, n+1):
6         dp[i] = dp[i-1] + dp[i-2]
7     return dp[n]

1 # 优化
2 def fib(n):
3     dp1 = dp2 = 1
4     for i in range(3, n+1):
5         dp1, dp2 = dp2, dp1+dp2
6     return dp2

凑零钱问题

 1 # 递归
 2 def coinChange(coins, amount):
 3     # 定义：要凑出金额n，至少要dp(n)个硬币
 4     def dp(n):
 5         # base case
 6         if n == 0: return 0
 7         if n < 0: return -1
 8         # 做选择，需要硬币最少的那个结果就是答案
 9         res = float('inf')
10         for coin in coins:
11             subproblem = dp(n - coin)
12             if subproblem == -1:
13                 continue
14             res = min(res, 1 + subproblem)
15         return res if res != float('inf') else -1
16     return dp[amount]

 1 def coinChange(coins, amount):
 2     memo = {}
 3     def dp(n):
 4         if n in memo:
 5             return memo[n]
 6         if n == 0:
 7             return 0
 8         if n < 0:
 9             return -1
10         res = float('inf')
11         for coin in coins:
12             subproblem = dp(n-cpin)
13             if subproblem == -1:
14                 continue
15             res = min(res, 1 + subproblem)
16 
17         memo[n] = res if res != float('inf') else -1
18     return dp(amount)

1 def coinChange(coins, amount):
2     dp = [amount + 1 for i in range(amount+1)]
3     for i in range(amount+1):
4         for coin in coins:
5             if i - coin < 0:
6                 continue
7             dp[i] = min(dp[i], 1 + dp[i - coin])
8     return -1 if dp[amount] == amount+1 else dp[amount]