动态规划 (动态编程DP) 教程

动态规划（Dynamic Programming ：DP、动态编程 、动态程序设计）被定义为一种在多项式时间内解决某些特定类型问题的技术。动态规划解决方案比指数暴力法更快，并且可以轻松证明其正确性。

动态编程主要是对普通递归的优化。无论何时我们看到重复调用相同输入的递归解决方案，我们都可以使用动态编程对其进行优化。

• DP想法是：简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。

动态规划算法的特点：

• 一般来说，动态规划（DP）是解决某一类问题的最强大的技术之一。 
• 有一种优雅的方式来制定该方法和一个非常简单的思维过程，并且编码部分非常简单。 
• 本质上，这是一个简单的想法，在使用给定输入解决问题后，将结果保存为参考以供将来使用，这样您就不必重新解决它..简单地说“记住您的过去”:)。 
• 如果给定的问题可以分解为更小的子问题，并且这些更小的子问题可以分解为更小的子问题，并且在这个过程中，你会看到一些重叠的子问题，这对DP来说是一个很大的提示。 
• 此外，子问题的最优解有助于给定问题的最优解（称为最优子结构属性）。
•  子问题的解决方案存储在表或数组中（记忆）或以自下而上的方式（制表）以避免冗余计算。
• 问题的解决方案可以由子问题的解决方案构建。
• 动态规划可以使用递归算法来实现，其中递归地找到子问题的解决方案，或者使用迭代算法来实现，其中通过按特定顺序处理子问题来找到解决方案。

• 表征最优解的结构，即建立解的数学模型。
• 递归地定义最优解的值。 
• 使用自下而上的方法，计算每个可能的子问题的最优解的值。
• 使用上一步中计算的信息构建原始问题的最佳解决方案。

涉及步骤：

• 自上而下（记忆）：分解给定的问题以便开始解决它。如果您发现问题已解决，请返回保存的答案。如果还没有解决，则解决并保存。这通常很容易想到并且非常直观，这被称为Memoization，见备忘录模式 或 缓存 模式 或 Fork-Join。
• 自下而上（DP、涌现 解决法）：分析问题并查看子问题的解决顺序，然后从琐碎的子问题逐步解决给定的问题。这个过程确保子问题先于主问题得到解决。这称为动态规划，使用制表tabulation储值。

两者对比：
有两种不同的方法来存储值，以便可以重用子问题的值。在这里，将讨论解决动态规划（DP）问题的两种模式： 

• 制表tabulation：自下而上，tabulation是一种自下而上的方法，我们将子问题的结果存储在表中，并使用这些结果来解决更大的子问题，直到解决整个问题。当我们可以将问题定义为一系列子问题并且子问题不重叠时，可以使用它。制表通常使用迭代来实现，非常适合具有大量输入的问题。
• 记忆Memoization：自上而下，记忆化是一种自上而下的方法，我们缓存函数调用的结果，如果使用相同的输入再次调用该函数，则返回缓存的结果。当我们可以将问题划分为子问题并且子问题具有重叠子问题时使用它。记忆化通常使用递归来实现，非常适合具有相对较小输入集的问题。

• 版本1：我将从Jdon学习DP理论，然后我将练习经典DP上的一些问题，从而掌握DP。
• 版本2：要掌握DP，我必须练习动态问题和练习问题 – 首先，我必须从Jdon学习一些DP理论

两者区别：

• 制表tabulation：将子问题的结果存储在表中，缓存的是子问题结果，这个子问题可能没有解决。
• 记忆Memoization：缓存函数调用的结果，因为是自上而下，只能将函数执行后的结果，解决方案的结果

制表tabulation Java实现

import java.util.Arrays;

public class Fibonacci {

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            int[] table = new int[n + 1];
            table[0] = 0;
            table[1] = 1;
            for (int i = 2; i <= n; i++) {
                table[i] = table[i - 1] + table[i - 2];
            }
            return table[n];
        }
    }

    public static void main(String[] args) {
        int n = 6; // Find the 6th Fibonacci number
        int result = fibonacci(n);
        System.out.println("The " + n + "th Fibonacci number is: " + result);
    }
}

在制表tabulation 实现中，我们使用一个名为 table 的数组来存储子问题的结果，并使用迭代来计算结果。

因为它从最底部的基本情况 table [0] 开始转换播放到达其目标状态 table [n]。在这里，我们可能会注意到 table 表是按顺序填充的，并且我们直接从表本身访问计算的状态，因此，我们将其称为制表tabulation 方法。 

Java代码记忆Memoization

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    public static int fibonacci(int n, Map<Integer, Integer> cache) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        int result;
        if (n == 0) {
            result = 0;
        } else if (n == 1) {
            result = 1;
        } else {
            result = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
        }

        cache.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 6; // Find the 6th Fibonacci number
        Map<Integer, Integer> cache = new HashMap<>();
        int result = fibonacci(n, cache);
        System.out.println("The " + n + "th Fibonacci number is: " + result);
    }
}

我们将最新的缓存存储到一个限制，这样如果下次我们收到来自相同状态的调用，我们只需从内存中返回它。因此，这就是为什么我们将其称为记忆化，因为我们正在存储最新的状态值。 

两种实现实现相同的结果，但使用的方法不同。记忆化Memoization是一种使用递归的自上而下的方法，而制表tabulation 是一种使用迭代的自下而上的方法。

状态

• 自上而下Memoization的设计：状态转移关系很容易想到。类似一个树，从树根开始分。这种方法属于演绎分析法。（DDD 领域驱动也属于这种自上而下，需要对领域划分子域，上下文BC，每个BC中有相应聚合状态。可以使用数据库字段表示状态）
• 而在自下而上tabulation 的思考中：由于思考处于下面细节上下文，无法从上面高处鸟瞰全局，因此，无法跳出上下文界限，而关注上下文之间的关系问题，因此状态转换关系很难思考。（这中思路是一种微服务思路，由于微服务架构不是由一个上帝总体划分，而是每个人都陷入具体微服务这个上下文中，这也是微服务与单体区别所在。可以使用事件溯源集合 然后通过播放某个状态）

识别问题：
为了动态地解决问题，我们需要检查两个必要条件： 

• 重叠子问题：当解决实际问题需要重复解决相同子问题时。据说该问题具有重叠子问题属性。
• 最优子结构性质：如果给定问题的最优解可以通过使用其子问题的最优解来获得，则称该问题具有最优子结构性质。

步骤：

1. 确定这是否是动态规划问题。
2. 使用最少参数确定状态表达式。
3. 制定状态和转换关系。
4. 做tabulation（或Memoization）。

如何形式化表达状态？
动态编程挑战中最难的部分就是这一步，需要大量的直觉、观察和训练。

举例说明

给定 3 个数字 {1、3、5}，任务是用给定的 3 个数字之和组成一个数字 N 的方法总数。(允许重复和不同的排列）。

1）组成 6 的方法总数是：8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1

2) 在所有可能的状态组合（n = 4）中加上 3；
[(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]

3) 将 5 加入所有可能的状态组合（n = 2）
[ (1+1) + 5]

(注意只需在右侧进行加法就足够了--所有从左侧进行加法的情况都已包括在同一状态或其他状态中，例如，[ 1+(1+1+1+3)] 在状态 (n=6) 中不需要，因为它已包括在状态 (n = 4) [(1+1+1+1) + 3] 中。）

现在，请仔细思考并确信上述三种情况涵盖了组成总和为 7 的所有可能方式；
因此，我们可以说：
state(7) = state (6) + state (4) + state (2) 
OR
state(7) = state (7-1) + state (7-3) + state (7-5)

抽象为： 
state(n) = state(n-1) + state(n-3) + state(n-5)

Java代码：

import java.io.*;

class GFG {

    // Returns the number of arrangements to
    // form 'n'.
    public static int solve(int n)
    {
        // base case
        if (n < 0)
            return 0;
        if (n == 0)
            return 1;

        return solve(n - 1) + solve(n - 3) + solve(n - 5);
    }
    public static void main(String[] args) {}
}

Python：

# Python program to Returns the number of arrangements to form 'n'
def solve(n):
# Base case
    if(n < 0):
        return 0
    if(n == 0):
        return 1
    return solve(n-1)+solve(n-3)+solve(n-5)

时间复杂性O(3n)，因为在每个阶段我们都需要做出三个决定，而树的高度将是 n 的数量级。
辅助空间：O(n)，递归调用堆栈会占用额外空间。

上述代码似乎是指数级的，因为它在重复计算相同的状态。因此，我们只需添加 memoization 即可。

为状态添加tabulation（或Memoization）
基于动态编程的解决方案的最简单部分就是这样。只需存储状态解决方案，我们就能在下次需要该状态时从内存中访问它。

Java代码：

// 存储状态值 初始化为 -1
int dp = new int[MAXN];

// This function returns the number of
// arrangements to form 'n'
int solve(int n)
{
    // base case
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;

    // Checking if already calculated
    if (dp[n] != -1)
        return dp[n];

    // 存储结果并返回
    return dp[n]
        = solve(n - 1) + solve(n - 3) + solve(n - 5);
}

Python3

# Initialize to -1
dp = []

# This function returns the number of
# arrangements to form 'n'
def solve(n):
    # base case
    if n < 0:
        return 0
    if n == 0:
        return 1

# Checking if already calculated
    if dp[n] != -1:
        return dp[n]

#  存储结果并返回
    dp[n] = solve(n-1) + solve(n-3) + solve(n-5)
    return dp[n]

时间复杂性：O(n)，因为我们只需调用 3n 个函数，而且不会重复计算，因为我们会返回之前计算的结果。
辅助空间：O(n)，递归调用堆栈会占用额外空间。