Search
当一个大题目是由多个子题目构成时，我们可以通过不绝分解题目来终极构建我们想求的大题目。这个过程成为搜索（Search）。
搜索空间（Search Space）可以用Tree的形式显现出来，便于明白。
时间复杂度取决于这棵树的深度和每个node的children个数。
Search 最告急的就是界说好状态，包管每个子题目都能用一个状态来形貌
Search没有重复子题目，但DP有。
DP（Dynamic Programming）
如果我们Search Space有重复子题目的话，可以纪录下这些子题目的答案来包管不会重复计算多次。以是DP也被称为Search+Memoization
云云一来，时间复杂度就取决于子题目的个数。
全部DP都可以写成Bottom Up DFS的形式。
小技巧：界说号状态后，可以从一个中心状态出发去思索递归规则
具体来说，动态规划的一般流程就是三步：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。
就思索流程来说，就分为一下几步：找到状态和选择 -> 明白 dp 数组/函数的界说 -> 探求状态之间的关系。
实例
/*一个呆板人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。呆板人每次只能向下大概向右移动一步。呆板人试图到达网格的右下角（在下图中标记为“Finish”）。问统共有多少条差异的路径？比方，上图是一个7 x 3 的网格。有多少大概的路径？示例1:输入: m = 3, n = 2输出: 3表明:从左上角开始，统共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右示例2:输入: m = 7, n = 3输出: 28提示：1 <= m, n <= 100题目数据包管答案小于便是 2 * 10 ^ 9 */class LeetCode62 { public static void main(String[] args) { //todo 动态规划-dp System.out.println(new Solution().uniquePaths(9, 8)); System.out.println(new Solution2().uniquePaths(9, 8)); System.out.println(new Solution3().uniquePaths(9, 8)); System.out.println(new Solution4().uniquePaths(9, 8)); } /* 思绪 思绪一：分列组合 由于呆板到底右下角，向下几步，向右几步都是固定的， 比如，m=3, n=2，我们只要向下 1 步，向右 2 步就肯定能到达止境。 以是有 C_{m+n-2}^{m-1}C m+n−2 m−1 Python def uniquePaths(self, m: int, n: int) -> int: return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1)) */ static class Solution { public int uniquePaths(int m, int n) { int[] cur = new int[n]; Arrays.fill(cur, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { cur[j] += cur[j - 1]; } } return cur[n - 1]; } } static class Solution2 { /* 思绪二：动态规划 我们令 dp[j] 是到达 i, j 最多路径 都有上一个和左一个决定 动态方程：dp[j] = dp[i-1][j] + dp[j-1] 注意，对于第一行 dp[0][j]，大概第一列 dp[0]，由于都是在边界，以是只能为 1 时间复杂度：O(m*n) 空间复杂度：O(m*n) 优化：由于我们每次只必要 dp[i-1][j],dp[j-1] 以是我们只要纪录这两个数，直接看代码吧！ */ public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < n; i++) dp[0] = 1; for (int i = 0; i < m; i++) dp[0] = 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] = dp[i - 1][j] + dp[j - 1]; } } return dp[m - 1][n - 1]; } } static class Solution3 { public int uniquePaths(int m, int n) { int[] pre = new int[n]; int[] cur = new int[n]; Arrays.fill(pre, 1); Arrays.fill(cur, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { cur[j] = cur[j - 1] + pre[j]; } pre = cur.clone(); } return pre[n - 1]; } } static class Solution4 { public int uniquePaths(int m, int n) { int[] cur = new int[n]; Arrays.fill(cur, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { cur[j] += cur[j - 1]; } } return cur[n - 1]; } }}/*给定一个包罗非负整数的 mxn网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。阐明：每次只能向下大概向右移动一步。示例:输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7表明: 由于路径 1→3→1→1→1 的总和最小。 */public class LeetCode64 { public static void main(String[] args) { //todo 动态规划-dp System.out.println(new Solution().minPathSum(new int[][]{ {1, 3, 1}, {1, 5, 1}, {4, 2, 1} })); System.out.println(new Solution().minPathSum2(new int[][]{ {1, 3, 1}, {1, 5, 1}, {4, 2, 1} })); } /* 思绪分析： -很显着，我们在遇到如许的统计可行路径的数目，大概求最小路径的时间，比力容易想到的两种做法，一个是搜索，另一个是动态规划 -而搜索的做法，仅仅在数据规模比力小的时间才思量使用，以是在这里，我们实行接纳动态规划来解决这个题目。 动态规划，告急关注以下两点 1，状态的设置。在这个题目里，由于要求最小路径和，我们可以令dp[j]代表从（i,j）走到（m-1,n-1）点的最小路径和 2，状态转移方程。我们思量怎样来求出dp[j]。由于每次只能往右或下走，以是(i,j)只能走到(i+1,j)大概(i,j+1)。 换言之，dp[j]的前续状态只有dp[i+1][j],dp[j+1],以是我们在两者取最小，然后加上这个格子内的数即可。 dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1)) */ static class Solution { public int minPathSum(int[][] grid) { int[][] dp = new int[grid.length][grid[0].length]; for (int i = grid.length - 1; i >= 0; i--) { for (int j = grid[0].length - 1; j >= 0; j--) { if (i == grid.length - 1 && j != grid[0].length - 1) dp[j] = grid[j] + dp[j + 1]; else if (j == grid[0].length - 1 && i != grid.length - 1) dp[j] = grid[j] + dp[i + 1][j]; else if (j != grid[0].length - 1 && i != grid.length - 1) dp[j] = grid[j] + Math.min(dp[i + 1][j], dp[j + 1]); else dp[j] = grid[j]; } } return dp[0][0]; } /* 动态规划-优化方法滚动数组 我们可以用一个一维数组来取代二维数组，dp数组的巨细和行巨细雷同。 这是由于对于某个固定状态，只必要思量下方和右侧的节点。 我们就可以一行一行计算，来节流空间复杂度。 */ public int minPathSum2(int[][] grid) { int[] dp = new int[grid[0].length]; for (int i = grid.length - 1; i >= 0; i--) { for (int j = grid[0].length - 1; j >= 0; j--) { if (i == grid.length - 1 && j != grid[0].length - 1) { dp[j] = grid[j] + dp[j + 1]; } else if (j == grid[0].length - 1 && i != grid.length - 1) { dp[j] = grid[j] + dp[j]; } else if (j != grid[0].length - 1 && i != grid.length - 1) { dp[j] = grid[j] + Math.min(dp[j], dp[j + 1]); } else { dp[j] = grid[j]; } } } return dp[0]; } }} |
