leetcode刷题之动态规划

leetcode刷题之动态规划 动态规划是leetcode刷题中的一种常见的算法思想，它通过将问题分解成小问题，解决小问题，然后将小问题的答案组合起来，解决原来的问题。动态规划的核心思想是将问题分解成小问题，然后将小问题的答案存储起来，以便于后续使用。 在动态规划中，我们通常使用数组来存储小问题的答案，这个数组被称为动态规划数组，简称dp数组。dp数组的每个元素dp[i]通常表示问题的子问题的答案，例如在爬楼梯问题中，dp[i]表示爬楼梯的第i个台阶的答案。 在实现动态规划时，我们需要遵循以下步骤： 1. 分解问题：将问题分解成小问题。 2. 定义dp数组：定义dp数组，dp[i]表示小问题的答案。 3. 初始化dp数组：初始化dp数组的初始值。 4. 迭代计算dp数组：迭代计算dp数组的每个元素，直到计算出整个dp数组。 5. 返回答案：返回dp数组的最后一个元素，即问题的答案。 下面我们将通过几个leetcode上的经典问题来介绍动态规划的应用。 爬楼梯 爬楼梯问题是leetcode上的一个经典问题，问题的描述是：给你一个整数n，你可以爬1步或2步，爬到第n个台阶需要多少步骤？ 我们可以使用动态规划来解决这个问题。我们定义dp数组，dp[i]表示爬到第i个台阶需要多少步骤。然后，我们可以根据以下公式计算dp数组： dp[i] = dp[i-1] + dp[i-2] 这个公式表示爬到第i个台阶需要多少步骤，可以爬1步或2步，所以我们需要计算爬到第i-1个台阶和第i-2个台阶的答案，然后将两者相加。 在实现时，我们可以使用以下代码： ```javascript var climbStairs = function(n) { let dp = new Array(n + 1); dp[0] = 0, dp[1] = 1, dp[2] = 2; for (let i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }; ``` 空间优化 在上面的实现中，我们使用了一个大小为n+1的数组来存储dp数组，这可能会导致空间浪费。我们可以使用空间优化的方法来减少空间的使用。 我们可以使用两个变量a和b来存储dp[i-1]和dp[i-2]的值，然后迭代计算dp[i]，最后返回dp[n]。 ```javascript var climbStairs = function(n) { let a = 1, b = 1, sum; for (let i = 0; i < n - 1; i++) { sum = a + b; a = b; b = sum; } return b; }; ``` 打家劫舍 打家劫舍问题是leetcode上的另一个经典问题，问题的描述是：给你一个整数数组nums，其中nums[i]表示第i个房屋的金额，你可以选择偷盗某些房屋，但不能偷盗相邻的房屋，求最大金额。 我们可以使用动态规划来解决这个问题。我们定义dp数组，dp[i]表示偷盗前i个房屋的最大金额。 ```javascript var rob = function(nums) { let n = nums.length; let dp = new Array(n + 1).fill(0); dp[0] = 0; dp[1] = nums[0]; for (let i = 2; i <= n; i++) { dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]); } return dp[n]; }; ``` 空间优化 同样，我们可以使用空间优化的方法来减少空间的使用。 ```javascript var rob = function(nums) { let n = nums.length; if (n === 0) return 0; let pre = 0, cur = 0; for (let i = 0; i < n; i++) { let temp = Math.max(cur, pre + nums[i]); pre = cur; cur = temp; } return cur; }; ``` 单词拆分 单词拆分问题是leetcode上的另一个经典问题，问题的描述是：给你一个字符串s和一个字符串数组wordDict，判断s是否可以由wordDict中的单词组成。 我们可以使用动态规划来解决这个问题。我们定义dp数组，dp[i]表示s的前i个字符是否可以由wordDict中的单词组成。 ```javascript var wordBreak = function(s, wordDict) { let n = s.length; let dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 0; i <= n; i++) { for (let j = 0; j <= i; j++) { if (dp[j] && wordDict.includes(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; }; ``` 这些问题都是leetcode上的经典问题，通过动态规划的思想，可以解决这些问题。