问题91 解码方法 ★☆☆☆☆ https://leetcode-cn.com/problems/decode-ways/ 对于这个题目，并不难想到用动态规划来解决，dp[i]表示长度为i的子串的解码方式数量，dp[1]根据s[0..0]是不是合法的编码值而初始化为1或0 ，dp[i+1]的值由dp[i], dp[i-1], s[i-1..i-1], s[i-2..i-1]四个值决定，代码...

问题70 爬楼梯 ★☆☆☆☆ https://leetcode-cn.com/problems/climbing-stairs/ 从动态规划的角度去考虑，还是很容易想到怎么解决这个问题的。从第1层到第i层，每次只能走1层或2层，所以无论怎么走，最终到第i层的可能走法就是到第i-2层的可能走法加上到第i-1层的可能走法之和。也就是说，就是Fibonacci数列。 public int c...

问题62 不同路径 ★★☆☆☆ https://leetcode.cn/problems/unique-paths/ 如果能想到以动态规划为思路来解决这个题目，那么这个题目并不难。状态转移方程也很符合直觉，定义dp[i][j]表示从[0, 0]到[i, j]的路径数，dp[i][j]的计算只依赖于dp[i-1][j]和dp[i][j-1]。 值得注意的是，这个题目容易给人一种适合于使用回...

问题337 打家劫舍 ★★☆☆☆ https://leetcode.cn/problems/house-robber-iii/ 这个题目有点意思，一开始我没搞清楚题目的意思，认为可行的解法是：给定一个节点，获取左子树的最大rob数，获取右子树的最大rob数，如果左子树和右子树最大rob数之和大于当前节点的val，那么返回它们的和作为当前节点的子树的最大rob数，否则，返回val作为当前节点...

问题198 打家劫舍 ★☆☆☆☆ https://leetcode-cn.com/problems/house-robber/ 这个题目从动态规划的角度考虑，并不难想到如何解决。我们定义一个dp数组，dp[i]表示num前i个元素对应的最大抢劫金钱数。那么如何从较小规模的dp元素值得到dp[i]的值呢？如果dp[i]对应的结果包含num第i个元素，那么最多抢劫到num[i-1]+dp[i-...

问题139 单词拆分 ★★★☆☆ https://leetcode-cn.com/problems/word-break/ 这个题目并不难想到使用动态规划，关键是状态转移方程。我们定义dp[i]表示字符串s的前i个字符对应的子串是否满足wordBreak，那么怎么得到dp[i+1]呢？如果dp[i]是true并且wordDict包含s[i, i+1]，那么dp[i+1]为true，或者如果...

问题120 三角形最小路径和 ★★☆☆☆ https://leetcode-cn.com/problems/triangle/ 从动态规划的角度去考虑，并不难想到如何解决这个问题。维护一个二维数组，dp[i][j]表示从top节点到第i行第j列的节点的最小路径sum，而dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]，这样从...

问题1105 填充书架 ★★☆☆☆ https://leetcode.cn/problems/filling-bookcase-shelves/ 这个题目，坦白讲，光理解题目意图就花了一定的时间，但是总结起来也不复杂。给定一组书，每本书有宽度和高度两个属性，还有一个固定宽度的书架，现在要把这些书按给定的顺序摆放到书架上，摆不开了就换层，求能实现摆放完所有书的最小总层高是多少。这里面有一个关...

问题81 搜索旋转排序数组 ★★☆☆☆ https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/ 这个题目和问题33几乎一样，差异点有两个： 问题33里数组元素是distinct的，即没有重复值，而问题81里数组元素可能有重复值； 问题33里rotation的位置是从第二个元素开始，即rotation后必然是两...

问题74 搜索二维矩阵 ★☆☆☆☆ https://leetcode-cn.com/problems/search-a-2d-matrix/ 这个题目其实就是把一个非递减序列的结构由一维数组换成了二维数组，问题的本质依然是二分查找，先按第一列做二分查找确认target所在行，再按行做二分查找。 public boolean searchMatrix(int[][] matrix, in...