算法学习：递归搜索与动态规划 笔记合集

好的，我将对您提供的内容进行整理和补充，以便更全面地了解和理解这些算法。

买卖股票的最佳时机

在买卖股票的最佳时机问题中，我们需要找到买入和卖出股票的最佳时机以获得最大利润。这个问题可以分为两个子问题：

1. 单次买卖股票的最大利润：

   • 给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。
   • 只允许完成一次交易（即只买入和卖出一次）。

   解题思路：

   • 使用动态规划来记录每一天结束时的最大利润。
   • 初始化一个二维数组 dp，其中 dp[i][j] 表示第 i 天持有/不持有股票的最大利润。
   • 状态转移方程：
     • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     • dp[i][1] = max(dp[i-1][1], -prices[i])

2. 多次买卖股票的最大利润：

   • 给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。
   • 允许完成尽可能多的交易（即可以无限次买入和卖出）。

   解题思路：

   • 使用动态规划来记录每一天结束时的最大利润。
   • 初始化一个二维数组 dp，其中 dp[i][j] 表示第 i 天持有/不持有股票的最大利润。
   • 状态转移方程：
     • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

3. 买卖股票的最佳时机含冷冻期：

   • 给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。
   • 允许完成尽可能多的交易（即可以无限次买入和卖出），但每次交易后需要冷静一天。

   解题思路：

   • 使用动态规划来记录每一天结束时的最大利润。
   • 初始化一个二维数组 dp，其中 dp[i][j] 表示第 i 天持有/不持有股票的最大利润。
   • 状态转移方程：
     • dp[i][0] = max(dp[i-1][0], dp[i-2][1] + prices[i])
     • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

Floyd算法

Floyd算法（Floyd-Warshall algorithm）用于计算图中各顶点之间的最短路径。其基本思想是通过逐步增加中间顶点，不断更新两点之间的距离。

具体步骤如下：

1. 初始化：

   • 创建一个二维数组 e，其中 e[i][j] 表示从 i 号顶点到 j 号顶点的最短路径长度。
   • 初始化 e[i][j] = graph[i][j]，即直接相邻的两点之间的距离。

2. 迭代：

   • 遍历所有可能的中间顶点 k（1 到 n）。
   • 对于每一对顶点 (i, j)，检查通过 k 作为中转点是否能获得更短的路径。
   • 更新 e[i][j] = min(e[i][j], e[i][k] + e[k][j])。

3. 结果：

   • 最终，e[i][j] 中存储的就是从 i 号顶点到 j 号顶点的最短路径长度。

示例代码：

function floydWarshall(graph) { let n = graph.length; let e = Array.from(Array(n), () => Array(n).fill(Infinity)); // 初始化 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { e[i][j] = graph[i][j]; } } // 迭代 for (let k = 0; k < n; k++) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { e[i][j] = Math.min(e[i][j], e[i][k] + e[k][j]); } } } return e; } 

通过以上代码和解释，您可以更全面地理解和应用这些算法。希望这些内容对您有所帮助！如果您有任何问题或需要进一步的解释，请随时告诉我。