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[i][j] 是到达 i, j 最多路径
       都有上一个和左一个决定
       动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
       注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

       时间复杂度：O(m*n)
       空间复杂度：O(m*n)

       优化：因为我们每次只需要 dp[i-1][j],dp[i][j-1]
       所以我们只要记录这两个数，直接看代码吧！
         */
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            for (int i = 0; i < n; i++) dp[0][i] = 1;
            for (int i = 0; i < m; i++) dp[i][0] = 1;
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][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[i][j]代表从（i,j）走到（m-1,n-1）点的最小路径和
    2，状态转移方程。我们考虑如何来求出dp[i][j]。由于每次只能往右或下走，所以(i,j)只能走到(i+1,j)或者(i,j+1)。
       换言之，dp[i][j]的前续状态只有dp[i+1][j],dp[i][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[i][j] = grid[i][j] + dp[i][j + 1];
                    else if (j == grid[0].length - 1 && i != grid.length - 1)
                        dp[i][j] = grid[i][j] + dp[i + 1][j];
                    else if (j != grid[0].length - 1 && i != grid.length - 1)
                        dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                    else
                        dp[i][j] = grid[i][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[i][j] + dp[j + 1];
                    } else if (j == grid[0].length - 1 && i != grid.length - 1) {
                        dp[j] = grid[i][j] + dp[j];
                    } else if (j != grid[0].length - 1 && i != grid.length - 1) {
                        dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
                    } else {
                        dp[j] = grid[i][j];
                    }
                }
            }
            return dp[0];
        }
    }
}