动态规划（Dynamic Programming，简称DP）是解决力扣（LeetCode）上许多算法问题的重要工具。它通过将复杂问题分解为重叠的子问题，并存储这些子问题的解来避免重复计算，从而实现高效求解。以下是一些破解力扣动态规划难题的核心技巧与策略。
一、动态规划基本思想
- 优化子结构：动态规划适用于那些可以将问题分解为子问题的问题，且这些子问题的解可以用来构建原问题的解。
- 最优子结构：原问题的最优解可以由子问题的最优解组合而成。
二、动态规划解题步骤
- 定义状态：确定DP数组（或表）中的状态代表什么。状态通常是对问题的某一方面的描述。
- 确定状态转移方程：找出状态之间的关系，通常是用来从一个状态计算出另一个状态的公式或规则。
- 初始化状态：设置边界条件，通常是最简单的情况或基础情况的解。
- 填充DP表：根据状态转移方程从初始状态开始，逐步计算出所有状态的解，直到得到原问题的解。
- 返回结果：最终的解通常会保存在DP表的某个位置，根据问题的要求返回相应的值。
三、经典动态规划题目解析
1. 最小路径和
题目描述：给定一个二维数组 grid，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。计算经过的路径和最小是多少。
解题思路：
- 定义状态：
dp[i][j]表示到达位置(i, j)的最小路径和。 - 状态转移方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。 - 初始化：
dp[0][0] = grid[0][0]，其他位置初始化为无穷大。 - 返回结果：
dp[m-1][n-1]。
2. 打家劫舍
题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，你希望偷窃得到的现金总额最大。但是，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
解题思路：
- 定义状态：
dp[i]表示偷窃前i个房屋所能获得的最大金额。 - 状态转移方程：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])。 - 初始化：
dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。 - 返回结果：
dp[n-1]。
3. 最长回文子串
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。
解题思路：
- 定义状态：
dp[i][j]表示字符串s中从索引i到j的子串是否为回文串。 - 状态转移方程：
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1])。 - 初始化：
dp[i][i] = true，dp[i][i+1] = (s[i] == s[i+1])。 - 返回结果：找到最长回文子串。
四、总结
通过以上技巧与策略，你可以更好地解决力扣上的动态规划难题。在学习过程中，多做题、多思考，逐渐掌握动态规划的核心思想和解题方法，相信你会在力扣上取得优异的成绩。