大学学风建设网站/网站应该如何推广

参考东哥的框架思维整理：
笔记：

• 首先，动态规划问题的一般形式就是求最值。
• 求解动态规划的核心问题是穷举。
• 动态规划的穷举有点特别，因为这类问题存在重叠子问题，如果暴力穷举的话效率会极其低下，所以需要备忘录或者 DP table来优化穷举过程，避免不必要的计算。
• 动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
• 虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。
• 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
• 基本框架如下：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：for 状态2 in 状态2的所有取值：for ...dp[状态1][状态2][...] = 求最值(选择1，选择2...)

零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：输入：coins = [2], amount = 3
输出：-1
示例 3：输入：coins = [1], amount = 0
输出：0
示例 4：输入：coins = [1], amount = 1
输出：1
示例 5：输入：coins = [1], amount = 2
输出：2提示：1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

代码：

class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""# 备忘录memo = dict()def dp(n):# 查备忘录，避免重复计算if n in memo: return memo[n]# base caseif n == 0: return 0if n < 0: return -1res = float('INF')for coin in coins:subproblem = dp(n - coin)if subproblem == -1: continueres = min(res, 1 + subproblem)# 记入备忘录memo[n] = res if res != float('INF') else -1return memo[n]return dp(amount)

小结：

1. 计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
2. 列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
3. 备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？