算法---动态规划

1.前言

哪些情况下会用到动态规划：

1.最优化问题：当需要求解最大值或最小值的问题时，可以考虑使用动态规划。例如，最长递增子序列、最短路径问题等。

2.问题具有重叠子问题性质：如果问题的解可以由其子问题的解构成，并且子问题之间存在重叠，即同一个子问题会被多次求解，那么可以使用动态规划。通过将子问题的解保存下来，避免重复计算，提高效率。

3.问题具有最优子结构性质：如果问题的最优解可以由其子问题的最优解推导得出，那么可以使用动态规划。通过递推关系式，将问题分解为子问题，并利用子问题的最优解来构造原问题的最优解。

4.求解过程具有重叠子结构性质：如果问题的求解过程中，需要多次用到相同的中间结果，那么可以使用动态规划。通过保存中间结果，避免重复计算，提高效率。

5.多阶段决策问题：当问题可以划分为多个阶段，并且每个阶段的决策依赖于之前阶段的决策结果时，可以使用动态规划。通过定义状态和状态转移方程，逐步求解每个阶段的最优解。

2. 斐波那契数列模型

示例 - 第N个泰波那契数

题目地址：点这里

2.1 算法原理（重点）

空间优化（选）：

• 背包问题
• 滚动数组

1. 创建一个长度为38的数组arr，用于存储计算过程中的中间结果。数组的下标表示泰波那契数的序号，数组元素存储对应序号的泰波那契数的值。

2. 初始化数组的前三个元素arr[0]、arr[1]和arr[2]分别为0、1、1，这是泰波那契数列的起始值。

3. 如果n小于等于2，直接返回arr[n]，即泰波那契数列的前三个数。

4. 从i=3开始，通过循环填充数组arr的剩余元素。对于每个i，计算泰波那契数arr[i]的值，它等于前三个数的和arr[i-3] + arr[i-2] + arr[i-1]。

5. 循环结束后，数组arr中的所有泰波那契数都已计算得到。

6. 返回arr[n]，即第n个泰波那契数的值。

2.2 代码

class Solution {
public:
    int tribonacci(int n) {
        //1.创建dp表
        int arr[38]={0};
        //2.初始化
        arr[0]=0,arr[1]=1,arr[2]=1;
        
        if(n<=2) return arr[n];
        
        int temp=0;
        //3.填表
        for(int i=3;i<=n;i++)
        {
            temp=arr[i-3]+arr[i-2]+arr[i-1];
            arr[i]=temp;
        }
        //4.返回值
        return arr[n];
    }
};

其他相关练习题：
使用最小花费爬楼梯
解码方法

3. 路径问题

动态规划（Dynamic Programming）是一种常用的解决优化问题的算法思想，它可以用于求解路径问题。路径问题通常是指在一个图或者矩阵中找到从起点到终点的最优路径，路径上可能会有一些限制条件或者权重。

下面我将介绍一个经典的动态规划路径问题——最短路径问题（Shortest Path Problem），以帮助你理解动态规划在路径问题中的应用。

最短路径问题是指在一个加权有向图中找到从起点到终点的具有最小权重和的路径。这里使用动态规划的思想来解决该问题，具体步骤如下：

1. 创建一个二维数组 dp，其中 dp[i][j] 表示从起点到达坐标 (i, j) 的最短路径权重和。
2. 初始化 dp 数组，将所有位置的值初始化为正无穷大。
3. 设置起点的路径权重为 0，即 dp[start_x][start_y] = 0。
4. 从起点开始进行动态规划计算，遍历图中的每个位置 (i, j)。

• 对于位置 (i, j)，我们可以通过上一个位置的最短路径来计算当前位置的最短路径。
• 计算方式为 dp[i][j] = min(dp[i][j], dp[i-1][j] + weight[i][j])，其中 weight[i][j] 表示从上一个位置到当前位置的权重。
• 同理，还需要考虑从左边的位置到当前位置的权重：dp[i][j] = min(dp[i][j], dp[i][j-1] + weight[i][j])。

5. 最终，dp[end_x][end_y] 即为从起点到终点的最短路径权重和。

上述步骤描述了如何使用动态规划求解最短路径问题。当然，具体问题的求解方法可能会有所不同，取决于问题的具体要求和限制条件。你可以根据实际情况进行调整和扩展。

相关练习题：
（不同路径2）
（下降路径最小和）
（地下城游戏）

4. 简单多状态 dp 问题

在动态规划中，有一类常见的问题被称为多状态动态规划问题（Multiple State DP Problems），也被称为简单多状态 DP 问题。这类问题中，我们需要维护多个状态变量，并根据这些状态变量的转移关系来求解最优解。

以下是一个简单的多状态动态规划问题的示例：背包问题（Knapsack Problem）。

背包问题是一个经典的优化问题，可以分为 0-1 背包和完全背包两种情况。这里以 0-1 背包问题为例进行说明。

问题描述：
假设有一个背包，容量为 C。现有 n 个物品，每个物品有两个属性：重量 w[i] 和价值 v[i]。要求在不超过背包容量的前提下，选择物品放入背包，使得背包中物品的总价值最大。

解决思路：

1. 创建一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时的最大总价值。
2. 初始化 dp 数组，将所有位置的值初始化为 0。
3. 从前往后遍历物品，对于每个物品 i，遍历背包容量 j。

• 若物品 i 的重量 w[i] 大于当前背包容量 j，则无法将物品 i 放入背包，因此 dp[i][j] = dp[i-1][j]，即当前状态的最优解与前一个物品的最优解相同。
• 若物品 i 的重量 w[i] 小于等于当前背包容量 j，则可以选择将物品 i 放入背包或不放入背包。两种情况下的最优解分别为：
  • 放入物品 i：dp[i][j] = dp[i-1][j-w[i]] + v[i]，即在剩余容量为 j-w[i] 时的最优解再加上物品 i 的价值 v[i]。
  • 不放入物品 i：dp[i][j] = dp[i-1][j]，即当前状态的最优解与前一个物品的最优解相同。
• 取两种情况下的最大值，即 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。

4. 最终，dp[n][C] 即为在前 n 个物品中，背包容量为 C 时的最大总价值。

上述步骤描述了如何使用动态规划求解 0-1 背包问题，其中涉及到了两个状态变量：物品的编号 i 和背包的容量 j。根据实际问题的不同，多状态动态规划问题可能会有更多的状态变量，并相应地设计状态转移方程。

相关练习题：
（按摩师）
（打家劫舍2）

总结解题思路

1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值