如何通过合约地址判断项目（七爪源码动态规划）
如何通过合约地址判断项目（七爪源码动态规划）让我们通过一个问题来理解上面讨论的整个过程。收集观察结果后，请使用以下框架来解决问题。最优子结构——如果可以通过使用其子问题的最优解来获得给定问题的最优解，则给定问题具有最优子结构属性。假设我们想找到从 Source 到 Destination 的最短路径。让 Via 成为 A 和 Source 之间的中间点，用一条边将其连接到 Source。但是我们有从 Via 到 Destination 的多条路径。在这种情况下，最短（源，目标）= min（源→通过 min（通过→目标））。重叠子问题——动态规划将解决方案组合到一次又一次需要的子问题上。 DP存储子问题的结果以避免重复计算。看到问题后，请执行以下步骤：
动态编程是对递归的增强！！！
DP == 递归 记忆（自上而下）或制表（自下而上）
识别 DP
寻找最大、最小、方式数或最佳等关键字。另一个提示是我们在每一步都有不同的选择/替代方案。然后寻找这个问题的答案，给定的问题是优化问题吗？
最优子结构——如果可以通过使用其子问题的最优解来获得给定问题的最优解，则给定问题具有最优子结构属性。假设我们想找到从 Source 到 Destination 的最短路径。让 Via 成为 A 和 Source 之间的中间点，用一条边将其连接到 Source。但是我们有从 Via 到 Destination 的多条路径。在这种情况下，最短（源，目标）= min（源→通过 min（通过→目标））。
重叠子问题——动态规划将解决方案组合到一次又一次需要的子问题上。 DP存储子问题的结果以避免重复计算。
看到问题后，请执行以下步骤：
- 可视化问题
- 查找子问题（后缀、前缀、子字符串）
- 找到子问题之间的关系
- 概括关系
- 实现子问题的顺序
收集观察结果后，请使用以下框架来解决问题。
让我们通过一个问题来理解上面讨论的整个过程。
爬楼梯
你正在爬楼梯。 到达顶峰需要 n 步。 每次您可以爬 1 或 2 级台阶。 您可以通过多少种不同的方式登顶？
解决DP问题的框架
1.定义目标函数
- f(n) 是到达第 n 个楼梯的不同方式的数量。
2. 识别基本案例最小有效输入
f(0) = 1
f(1) = 1
f(2) = 2 # f(2) can be caluculated from f(0) and f(1) as well. I have taken this just for more clarity.
3. 写下目标函数的递推关系。
f(n) = f(n-1) f(n-2)
注意：在递归中，我们一般会在每个后续函数调用中减少输入空间。 这里我们正在减少 n，如果我们有一个数组，我们可以通过增加索引（从左到右）或减少索引（从右到左）来减小数组大小。
4. 执行顺序是什么？
n → n-1 → n-2 … 1 → 0
5. 在哪里寻找答案？
f(n)
递归解决方案
class Solution:
def climbStairs(self n):
return self.cs_helper(n)
def cs_helper(self n):
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
return self.cs_helper(n - 1) self.cs_helper(n - 2)
递归 记忆
不记得过去的人，注定要重蹈覆辙。
我们使用数组来存储计算参数的结果，而不是一次又一次地使用相同的参数调用函数。
class Solution:
def climbStairs(self n):
memo = [None for i in range(n 1)]
return self.cs_helper(n memo)
def cs_helper(self n memo):
if memo[n] is not None:
return memo[n]
if n == 0:
return 0
if n == 1:
result = 1
if n == 2:
result = 2
else:
result = self.cs_helper(n - 1 memo) self.cs_helper(n - 2 memo)
memo[n] = result
return result
自下而上/制表
现在我们按照框架将递归解决方案转换为线性解决方案。 由于我们使用 0、1 和 2 第二步的基本情况，我们用值 0、1、2 初始化 dp[0]、dp[1] 和 dp[2]。函数调用更改为 dp[n ] 分配，它使用最后两个位置 (dp[n-1] & dp[n-2]) 作为查找来获得答案。
class Solution:
def climbStairs(self n):
dp = [0] * (n 1)
dp[0] dp[1] dp[2] = 0 1 2
for i in range(3 n 1):
dp[i] = dp[i-1] dp[i-2]
return dp[n]
在上述解决方案中，我们使用的顺序为 0 → 1 →2 →3… →n-1 →n。
DP中的空间优化
由于在每个索引处我们只查找最后两个值，我们可以删除 DP 数组并仅使用两个变量来获得结果。
class Solution:
def climbStairs(self n):
first = 1
second = 1
for i in range(2 n 1):
res = first second
first second = second res
return second
自上而下和自下而上方法之间的主要区别在于，后一种方法计算所有解决方案，而第一种方法仅计算所需的解决方案。 在自下而上的方法（制表法）中，我们可以优化递归解决方案中不可能的空间复杂度。
快乐编码！
关注七爪网，获取更多APP/小程序/网站源码资源！
