Java动态规划知识点（含面试大厂题和源码）

动态规划（Dynamic Programming, DP）是一种算法思想，用于解决具有重叠子问题和最优子结构特性的问题。通过将大问题划分为较小的子问题，并存储已解决子问题的结果（通常是在一个表格中）来避免重复计算，动态规划能够有效地减少计算量，提高算法效率。

动态规划的关键概念

• 重叠子问题：在求解过程中，同一问题多次出现。
• 最优子结构：问题的最优解包含其子问题的最优解。
• 状态：表示问题解决的一个阶段或者情形。
• 状态转移方程：定义了状态之间的关系，描述了如何从一个或多个较小的子问题的解得到更大的子问题的解。

解题步骤

1. 定义状态：找出问题的变量和参数，这将决定状态的定义。
2. 建立状态转移方程：找出状态之间如何转移，即每个状态是如何通过其他状态得到的。
3. 确定初始条件和边界情况：确定动态规划表的起点和如何处理边界情况。
4. 计算顺序：确定状态计算的顺序，以确保在计算一个状态时，所需的所有状态都已计算并存储。
5. 解决问题：使用定义的状态转移方程，从初始状态计算到目标状态。

常见的动态规划类别

• 线性动态规划：如斐波那契数列、最长公共子序列。
• 区间动态规划：如矩阵链乘法、最优二叉搜索树。
• 背包问题：如0-1背包、完全背包、多重背包。
• 树形动态规划：在树形数据结构上应用的动态规划。
• 状态压缩动态规划：当状态可以用位表示时，使用位运算来优化空间和时间复杂度。
• 路径动态规划：如在网格上找到从一点到另一点的最短/最长路径。

动态规划的优化

• 空间优化：通过滚动数组等技巧减少空间复杂度。
• 状态压缩：通过位操作压缩状态，减少存储需求。
• 分治法结合动态规划：用分治法解决部分动态规划问题，提高效率。
• 记忆化搜索：动态规划的一种实现方式，结合递归和缓存已计算结果来避免重复计算。

动态规划是解决优化问题的强大工具，特别是当问题可以被分解为相关子问题时。熟练掌握动态规划不仅可以帮助你解决复杂的编程问题，也是算法面试中常考的重点之一。

题目1：爬楼梯（动态规划）

题目描述：假设你正在爬楼梯。需要 n 步你才能到达顶部。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到顶部呢？

解法代码（Python）：

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    first, second = 1, 2
    for i in range(3, n + 1):
        third = first + second
        first, second = second, third
    return second

# 示例
print(climbStairs(3))  # 输出: 3
1
2
3
4
5
6
7
8
9
10
11

题目2：最大子序和（数组）

题目描述：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解法代码（Python）：

def maxSubArray(nums: List[int]) -> int:
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# 示例
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9

题目3：有效的括号（字符串）

题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

解法代码（Python）：

def isValid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

# 示例
print(isValid("()[]{}"))  # 输出: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这些题目涵盖了基本的算法和数据结构知识，是准备算法面试时的好练习。理解这些题目的解题思路和代码实现，能帮助你在面试中更加自信地解答类似的问题。