算法入门很简单：动态规划入门

何时应该使用动态规划

当我们看到像这样的术语时：

“最短/最长，最小/最大，最小/最大，最小/最大，“最大/最小”

我们知道这是一个优化问题。

动态规划算法正确性的证明通常是不言而喻的。其他算法策略通常很难证明是正确的。因此，更容易出错。

当我们看到这些种类的术语时，问题可能会要求一个特定的数字（“查找最小数量的编辑操作”），也可能会要求一个结果（“查找最长的公共子序列”）。后一种类型的问题很难识别为动态编程问题。如果听起来像是优化，动态编程可以解决它。

想象一下，我们发现了一个问题，这是一个优化问题，但是我们不确定是否可以使用动态编程来解决。首先，确定我们要优化的内容。一旦意识到要优化的内容，我们必须决定进行优化的难易程度。有时，贪婪的方法足以提供最佳解决方案。动态编程采用蛮力方法。它确定重复的工作，并消除重复。

核心——“记忆化”

动态编程的核心思想是通过记住部分结果来避免重复工作，该概念将其应用于许多现实生活中。

动态规划和递归

动态规划 = 递归 + 常识

递归： 允许您根据函数的其他值来表达该函数的值

常识： 如果预先完成函数的递归调用方式，然后存储以便快速访问，则可以使得程序变得更快。

这就是我们所说的“记忆化”-记忆某些特定状态的结果，然后可以访问这些状态以解决其他子问题。

动态规划背后的直觉是我们为时间交换了空间，也就是说，与其花大量时间却没有空间来计算所有状态，我们不占用空间来存储所有子问题的结果以节省时间。。

让我们来看一下斐波那契数列的例子：

Fibonacci (n) = 1; if n = 0
Fibonacci (n) = 1; if n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

所以斐波那契数列的值将会是: 1, 1, 2, 3, 5, 8, 13, 21… 一直延续下去！

使用纯递归的代码：

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

使用带有备注的动态规划方法：

def fibonacciVal(n):
		memo[0], memo[1] = 0, 1
		for i in range(2, n+1):
			memo[i] = memo[i-1] + memo[i-2]
		return memo[n]

def fib2(n):

    fib_list = [1 ,1]
    while len(fib_list) < n + 1:
        fib_list.append(0)
    
    if n <= 1:
        return n
    else:
        if fib_list[n-1] == 0:
            fib_list[n-1] = fib2(n-1)

        if fib_list[n-2] == 0:
            fib_list[n-2] = fib2(n-2)

    fib_list[n] = fib_list[n-1] + fib_list[n-2]
    return fib_list[n]

大多数动态规划问题可以分为两类：:

1. 优化问题.

2. 组合问题.

优化问题要求您选择一个可行的解决方案，以使所需功能的值最小化或最大化。

组合问题要求您弄清楚做某事的方式数量，或某些事件发生的可能性。

每个动态编程问题都有一个要遵循的架构：

• 表明该问题可以分解为最优子问题。
• 通过针对较小的子问题的最佳解来表达解的值，从而递归定义解的值。
• 以自下而上的方式计算最佳解决方案的价值。
• 根据所计算的信息构造最佳解决方案。

自底而上 vs. 自上向下:

• 自下而上-我将学习编程。然后，我将开始练习。然后，我将开始参加比赛。然后，我将练习更多并尝试改进。在疯狂地工作之后，我将成为一名了不起的程序员。
• 自上而下-我将成为一名了不起的程序员。怎么样？我会疯狂地工作。怎么样？我会练习更多，并尝试改进。怎么样？我将开始参加比赛。然后？我会练习怎么样？我将学习编程。

这不是一个很好的例子，但我希望我能理解我的意思。在“自上而下”中，您将通过解释如何从较小的解决方案中构建来立即开始构建大型解决方案。在“自下而上”中，您将从小型解决方案开始，然后进行构建。

记忆化很容易编码，可能会成为您一段时间内的首选方法。尽管使用动态编程，您不会冒着耗尽堆栈空间的风险，但您最终可以自由地放弃计算。缺点是你必须想出一个有效的解决方案的顺序。

可以将动态编程视为一种表填充算法：您知道必须执行的计算，因此您选择了执行它们的最佳顺序，而忽略了不必填充的那些计算。

让我们来看一个简单的问题：

假设给你一个数字 N，你必须找出不同写法的数量，即 1、3 和 4 的总和。

例如, 如果 N = 5, 这个结果将会是 6.

• 1 + 1 + 1 + 1 + 1
• 1 + 4
• 4 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 + 1 + 1

子问题: DPn 是将 N 写为 1、3 和 4 之和的方式数。
找到递归: 考虑一种可能的解决方案，n = x1 + x2 + … xn。如果最后一个数字是 1，则其余数字的总和应该是 n - 1。因此，以 1 结尾的和的数量等于 DPn-1……考虑最后一个数字是 3 和 4 的其他情况。最终重现将是：:

DPn = DPn-1 + DPn-3 + DPn-4.

考虑基本情况： DP0 = DP1 = DP2 = 1, and DP3 = 2.

实现算法:

 	DP[0] = DP[1] = DP[2] = 1; 
 	DP[3] = 2;
    for (i = 4; i <= n; i++) {
      DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
    }

上述技术采用自下而上的方法，并使用记忆化来不计算已经计算过的结果。

总结

综上所述，如果您确定可以使用 DP 解决问题，请尝试创建一个回溯函数来计算正确答案。尽量避免冗余参数，最小化函数参数的可能值范围，并尝试优化一个函数调用的时间复杂度（请记住，您可以将递归调用视为在 O(1) 时间内运行）。

最后，您可以记住这些值，并且不要两次计算相同的东西。