动态规划解题策略与C++刷题心得

“c++算法刷题笔记.pdf” 这篇文档是关于C++算法的学习笔记，特别关注动态规划这一重要算法主题，旨在帮助读者提高算法能力，为进入大型科技公司（大厂）做准备。作者强调了刷题的重要性，认为数量不是关键，关键是每次解题后的反思和总结。 动态规划是一种解决复杂问题的有效方法，它通过将问题分解成更小的子问题来求解。在数学、管理科学、计算机科学等多个领域都有应用。动态规划的优势在于处理有重叠子问题和最优子结构的问题，通常比朴素解法更高效，因为它避免了重复计算。 动态规划的基本思想是分治，即先解决子问题，再组合子问题的解来得到原问题的解。这种方法特别适合优化递归问题，例如斐波那契数列。通过记忆化存储已解决的子问题，动态规划可以显著减少计算量，尤其在子问题的数量随输入规模指数增长时。 文档中给出了一个具体的动态规划应用实例——“岛屿的最大面积”。这个问题要求在给定的二维网格（grid）中，找到由1（代表陆地）组成的岛屿的最大面积。每个岛屿由相邻的1构成，且相邻是指水平或垂直方向。网格的边缘被水包围，意味着岛屿不会扩展到边界之外。 解决这个问题的方法是采用深度优先搜索（DFS）或广度优先搜索（BFS）策略，从每个1开始探索，标记已访问过的陆地，直到遇到水或已访问过的陆地为止。然后，计算当前岛屿的面积，并与之前找到的最大面积进行比较，保留较大值。这个过程对grid中的每个1执行一次，最后返回的最大面积就是所有岛屿中的最大面积。 在这个例子中，`maxAreaOfIsland`函数遍历整个grid，对于每个元素，调用`area`函数来计算相应位置开始的岛屿面积。`area`函数可能使用DFS或BFS来探索相邻的陆地并计算面积。这个算法的关键在于有效地跟踪和更新最大面积，同时避免回溯到已访问过的陆地，以确保效率。 通过这样的实践和总结，读者不仅可以掌握动态规划的理论知识，还能提升实际编程解决问题的能力。对于C++程序员来说，理解和熟练运用动态规划是提高算法技能和解决实际问题的关键步骤。