LeetCode热题100——动态规划（一句话题解及复杂度分析）

解题步骤（爬楼梯为例）：

1、定义子问题：原始问题为有多少种方法可以爬到第n个台阶（楼顶）。可以将其转换为有多少种方法可以爬到第i个台阶，方法数为f(i)；

2、写出子问题的递推关系：在动态规划问题中，子问题是存在递推关系的（f(i)应该可以用之前的元素进行表示），例如在爬楼梯中，F(i) = F(i-1) + F(i-2)；

3、构建并更新dp数组：动态规划问题可以自顶向下用递归做，也可以自底向上用遍历的方式做。这里我们全部采用后者，构建dp数组来保存中间的所有计算结果避免重复计算。例如在爬楼梯中，我们可以用dp数组来记录F(i-1)和F(i-2)，这样在每次循环中只需要用O(1)的复杂度计算F(i)并且更新dp数组即可，不需要再多次计算前面的值。

4、空间优化（可选，不影响题目通过）：对于不再用到的dp数组，我们可以直接删掉。例如在爬楼梯中，当计算F(10)时，会用到F(9)和F(8)，此时F(1)和F(2)等前面的元素已经不会再用到了，因此整个过程中我们其实可以只使用两个变量来保存dp数组，并在每次循环时更新这两个值。

70.爬楼梯

Q：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

A：假设F(n)为爬上第n个台阶有多少种方法则有递推公式：

F(n)=F(n-1)+F(n-2)

为了避免索引越界（索引为-1的情况），我们初始化F(0)和F(1)都为1。创建一个dp数组来记录爬上每个下标的台阶有多少种方法（例如爬上第3个台阶有dp[3]种方法），用dp来记录之前的计算结果避免重复计算。

class Solution { public int climbStairs(int n) { // 用dp数组存储爬到对应下标的台阶有多少种方法 int[] dp = new int[n + 1]; // 以第0个和第1个台阶作为起始计算点 dp[0] = 1; dp[1] = 1; // 计算爬上第i个台阶有多少种方法 for(int i = 2; i <= n; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}

时间复杂度：O(n)——只进行了一次循环

空间复杂度：O(n)——创建了一个空间问n的数组

118.杨辉三角

Q：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

A：在杨辉三角的第i行中（假设i从0开始），一共有i+1个元素，其中下标为0和i（第一个和最后一个）的元素值都为1；对于其他元素，例如第j个元素，其值等于第i-1行的下标为j-1和j的元素之和。公式如下：

class Solution { public List<List> generate(int numRows) { List<List> ans = new ArrayList(); for(int i=0; i<numRows; i++){ List row = new ArrayList(); // 第i行（i从0开始）一共有i+1个数 for(int j=0; j<i+1; j++){ // 对于每一行第一个和最后一个，直接添加“1” if(j==0 | j==i){  row.add(1); }else{  row.add(ans.get(i-1).get(j-1) + ans.get(i-1).get(j)); } } ans.add(row); } return ans; }}

时间复杂度：O(n^2)——进行了嵌套循环

空间复杂度：O(n^2)——创建了一个嵌套的List结构，且元素数量和输入有关

198.打家劫舍

Q：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

A：创建子问题，用F(i)表示在不触动警报的前提下偷前i间房子能偷到的最高金额；此时有两种情况——偷最后一间房子nums[i]不偷倒数第二间房子；不偷最后一间房子偷倒数第二间房子nums[i-1]，F(i)应该为这两个值中较大的值，递推关系如下：

F(i) = Math.max(F(i-1), F(i-2) + nums[i])

创建dp_arr来保存每一个F(i)，这里dp数组的大小我们选择n+1（n为总共的房子数）目的是方便进行初始化。假如我们使用n作为dp数组的大小，那么当房子数为1的时候，我们无法初始化dp数组的前两个值（下标越界）。

class Solution { public int rob(int[] nums) { int n = nums.length; int[] dp_arr = new int[n+1]; // dp数组,dp[i]表示偷前i个房子最多能偷多少钱 dp_arr[0] = 0; // 偷前0个房子 dp_arr[1] = nums[0]; // 偷前1个房子 for(int i=2; i<n+1; i++){ // 子问题递推关系 dp_arr[i] = Math.max(dp_arr[i-1], dp_arr[i-2]+nums[i-1]); } return dp_arr[n]; }}

时间复杂度：O(n)——进行了一次循环

空间复杂度：O(n)——创建了一个dp数组（此处可优化为O1）

279.完全平方数

Q：给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

A：假设最少用F(i)个完全平方数相加可以得到i，那么对于子问题j，我们有递推公式：

F(i) = min(F(i), F(i-j*j)+1)

在这条公式中，j*j表示小于i的完全平方数（例如对于i=17来说，j可以为1、2、3、4，j*j<=i）；

对于每一个i我们都需要从1开始遍历一遍所有可能的完全平方数；

我们将F(i)初始化为i（最大值，可以用i个1来表示这个数）；

对于每一个j，i可以由1个j*j加上F(i-j*j)个数相加来表示（例如17可以由1个4*4加上F(1)个数来表示，也可以由1个3*3加上F(8)个数来表示）

class Solution { public int numSquares(int n) { int[] dp = new int[n+1]; dp[0] = 0; for(int i=1; i<n+1; i++){ dp[i] = i; // dp数组初始化（最大值为全用1来表示一个数本身） for(int j=1; j*j<=i; j++){ // 递推公式 dp[i] = Math.min(dp[i], dp[i-j*j]+1); } } return dp[n]; }}

时间复杂度：O(n*sqrt(n))——嵌套循环，在内部循环中只用了平方根级别的次数

空间复杂度：O(n)——创建了一个dp数组

322.零钱兑换

Q：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

A：这题跟上一题完全平方数非常相似，唯一不同的是这里有可能没有一种硬币组合能组成总金额。递推方程：对于F(i)表示组成总金额i所需的最少硬币个数，有：

F(i) = min(F(i), 1+F(i-coins[j]))

其中j为硬币数组coins的下标，我们需要初始化dp数组为一个很大的值（F(0)=0除外），在遍历更新完dp数组后，如果dp(n)大于amount，说明没有硬币能组合成amount，返回-1。

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; Arrays.fill(dp, amount+1); dp[0] = 0; for(int i=1; i<amount+1; i++){ for(int j=0; j=coins[j]){ // 检查硬币是否小于当前数值  dp[i] = Math.min(dp[i], 1+dp[i-coins[j]]); } } } return dp[amount]>amount ? -1 : dp[amount]; }}

时间复杂度：O(n*l)——嵌套循环，外循环循环amount次，内循环循环amount.length次

空间复杂度：O(n)——dp数组大小为amount+1

139.单词拆分

Q：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

A：

转换子问题：我们可以将字符串s看成字符数组，用F(i)表示字符串前i个字符组成的子串能否用字典组合而成。例如对于字符串\"leetcode\"，F(4)表示子串\"leet\"能否用字典组合而成，结果是true。

递推公式：拿到一个字符串，我们遍历字典，以此看看该字符串能否以字典中的小字符串结尾，例如对于字符串\"leetcode\"，求F(8)时，我们看看字符串能否以字典中的小字符串结尾(使用endsWith方法)，如果能，则F(8)=F(8-4)，4为匹配到的小字符串长度。遂有公式：

当结尾匹配上子字符串sub_s时，F(i) = F(i - sub_s.length())

我们可以初始化整个dp数组为flase，只有dp[0]为true，这样当未匹配上时，我们不需要进行额外处理，结果默认就是false。

class Solution { public boolean wordBreak(String s, List wordDict) { boolean dp[] = new boolean[s.length()+1]; Arrays.fill(dp, false); // 初始化 dp[0] = true; for(int i=1; i<s.length()+1; i++){ // 遍历从头开始的s的子串 for(int j=0; j<wordDict.size(); j++){ // 遍历字典 if(s.substring(0, i).endsWith(wordDict.get(j))){ // 如果结尾能匹配上  dp[i] = dp[i]==true ? true : dp[i-wordDict.get(j).length()]; // 更新dp数组 } } } return dp[s.length()]; }}

时间复杂度：O(n*l)——嵌套循环，外循环循环s.length()次，内循环循环wordDict.size()次

空间复杂度：O(n)——dp数组大小为s.length()+1

300.最长递增子序列

Q：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

A：我们用F(i)来表示以nums[i]结尾的最长子序列长度，如果说nums[i]>nums[i-1]，则nums[i]可以插入到nums[i-1]后面，那么有：

F(i) = F(i-1) + 1

如果nums[i]<=nums[i-1]，则nums[i]无法插入到nums[i-1]后面，那么以nums[i]结尾的最长子序列的长度只能为1（子序列只有一个数字）。最终我们要求的最长子序列长度不一定以数组的最后一个元素结尾，所以我们不返回dp[nums.length+1]，而是返回整个遍历过程中dp数组的最大值。

class Solution { public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length+1]; Arrays.fill(dp, 1); dp[0] = 1; int ans = 1; for(int i=1; i<nums.length+1; i++){ for(int j=1; j nums[j-1]) dp[i] = Math.max(dp[i], dp[j]+1); } ans = Math.max(ans, dp[i]); } return ans; }}

class Solution { public int maxProduct(int[] nums) { int[] dp_max = new int[nums.length+1]; // 用来记录以i结尾的子数组的最大值 int[] dp_min = new int[nums.length+1]; // 用来记录以i结尾的子数组的最小值 dp_max[0] = 1; dp_min[0] = 1; int res = Integer.MIN_VALUE; // 我们求的结果不一定以nums[nums.length-1]结尾，所以要维护一个记录最大值的变量 for(int i=1; i0){ // 判断当前元素是正数还是负数 dp_max[i] = Math.max(nums[i-1], dp_max[i-1]*nums[i-1]); dp_min[i] = Math.min(nums[i-1], dp_min[i-1]*nums[i-1]); }else{ dp_max[i] = Math.max(nums[i-1], dp_min[i-1]*nums[i-1]); dp_min[i] = Math.min(nums[i-1], dp_max[i-1]*nums[i-1]); } res = Math.max(res, dp_max[i]); } return res; }}

class Solution { public boolean canPartition(int[] nums) { int sum = 0; int max = 0; for(int i=0; isum/2) return false; int target = sum/2; // 创建二维dp数组 boolean[][] dp = new boolean[nums.length][target+1]; for(int i=0; i<nums.length; i++){ Arrays.fill(dp[i], false); dp[i][0] = true; // 初始化考虑j=0的边界 } dp[0][nums[0]] = true; // 初始化考虑到i=0的的边界 for(int i=1; i<nums.length; i++){ for(int j=0; j j) dp[i][j] = dp[i-1][j]; else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]; } } return dp[nums.length-1][target]; }}

class Solution { public int longestValidParentheses(String s) { int[] dp = new int[s.length()+1]; Arrays.fill(dp, 0); // 初始化dp数组，主要是dp[0]和dp[1]要是0 int max = 0; for(int i=2; i-1 && s.charAt(i - dp[i-1] - 1 - 1) == \'(\'){ dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2];  } } } max = Math.max(dp[i], max); } return max; }}