1、常见题型（上）.md

### 典例

#### [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)

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

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

注意：给定 n 是一个正整数。



示例 1：

```
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶
```

示例 2：

```
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
```



**题解**

<img src="https://img-blog.csdnimg.cn/20210210231028707.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70"  width="45%"/>

```java
class Solution {
    int[] cache = null;

    public int climbStairs(int n) {
        cache = new int[n + 1];
        return func(n);
    }

    int func(int n){
        int res = 0;
        if((res = cache[n]) != 0){
            return res;
        }

        if(n == 1){
            res = 1 ;
        }else if(n == 2){
            res = 2;
        }else{
            res = func(n -1) + func(n -2);
        } 

        cache[n] = res;
        return res;
    }
}
```







#### [120. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/)

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

示例 1：

```
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
```

示例 2：

```
输入：triangle = [[-10]]
输出：-10
```



**法一：记忆化搜索**

* 递归程序编写核心：明确**递归树每个节点的含义**，该含义也是每次递归入参，且也会根据这个条件判断终止情况

  * 例如 fb 的递归树，每个节点的含义是 n

    
	<img src="https://img-blog.csdnimg.cn/20210210231047795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70"  width="45%"/>

  * 例如 mergeSort ，每个节点的含义是 size

	<img src="https://img-blog.csdnimg.cn/2021021023110723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70"  width="45%"/>

  * 例如 这道题，每个节点的含义是 层次和在层次中的索引

* 明确**递归要从递归树的根节点开始**

  * 递归树每个节点的操作是：**直接继续递归获得子节点的值，然后跟自己的值进行操作**

```java
class Solution {
    // 注意：这里是一个优化，不使用 map 作为 cache ，使用数组
    Integer[][] cache;

    public int minimumTotal(List<List<Integer>> triangle) {
        cache = new Integer[triangle.size()][triangle.size()];
        return func(triangle , 0 ,0);
    }

    int func(List<List<Integer>> triangle , int level , int idx){
        Integer res = null;
        if((res = cache[level][idx]) != null){
            return res;
        }

        if(level == triangle.size() - 1){
            res = triangle.get(level).get(idx);
        }else{
            int l = func(triangle , level + 1, idx);
            int r = func(triangle , level + 1, idx + 1);
            res = triangle.get(level).get(idx) + Math.min(l, r);
        }

        cache[level][idx] = res;
        return res;
    }
}
```



**法二：动态规划**

* 由自顶向下的搜索，变为自底向上的递推
* 和上面那个 dfs 深搜没有本质区别，深搜也是搜到底然后向上反馈

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
        for(int i = triangle.size() - 1; i >= 0  ; i --){
            for(int j = 0 ; j < triangle.get(i).size() ; j ++){
                dp[i][j] = Math.min(dp[i + 1][j] , dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }

        return dp[0][0];
    }
}
```



#### [64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)


给定一个包含非负整数的 `*m* x *n*` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：** 每次只能向下或者向右移动一步。



**题解**

* 核心：
  * 还是上面说的要清楚递归树，明白每个递归节点的含义
  * 对于可达性说明：只要递归树可达，那么一定可达（因为递归树也代表着路径，并且每个子节点的返回值已经代表了从这个节点下去时，路径的最值）

* 注意边界
  * 要避免 Math.min 会选中不可达的 

```java
class Solution {

    Integer[][] cache = null;

    public int minPathSum(int[][] grid) {
        cache = new Integer[grid.length][grid[0].length];
        return dfs(grid , 0 , 0);
    }

    int dfs(int[][] grid , int level , int idx){
        if(level == grid.length || idx == grid[level].length){
            return Integer.MAX_VALUE;
        }
        
        Integer res = 0;
        if((res = cache[level][idx]) != null){
            return res;
        }

        int l = dfs(grid , level + 1 , idx);
        int r = dfs(grid , level , idx + 1);

        if(level == grid.length - 1 && idx == grid[level].length - 1){
            res = grid[level][idx];
        }else{
            res = grid[level][idx] + Math.min(l , r);
        } 

        cache[level][idx] = res;
        return res;
    }
}
```



#### [343. 整数拆分](https://leetcode-cn.com/problems/integer-break/)

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

```
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
```

示例 2:

```
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
```



**题解**

* 要弄清当前状态可以转移到多少种不同状态


	<img src="https://img-blog.csdnimg.cn/20210210231128250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70"  width="45%"/>




```java
class Solution {
    int[] cache = null;
    public int integerBreak(int n) {
        cache = new int[n + 1];
        return dfs(n);
    }

    int dfs(int n){
        if(cache[n] != 0){
            return cache[n];
        }

        int max = 1;
        for(int i = 1 ; i < n ; i ++){
            int res = dfs(i);
            res = Math.max(res, i);
            max = Math.max(max , res * (n - i));
        }

        cache[n] = max;
        return max;
    }

}
```



 #### [279. 完全平方数](https://leetcode-cn.com/problems/perfect-squares/)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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



示例 1：

```
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
```


示例 2：

```
输入：n = 13
输出：2
解释：13 = 4 + 9
```

提示：

`1 <= n <= 104`



**题解**

```java
class Solution {
    int[] cache = null;
    public int numSquares(int n) {
        cache = new int[n + 1];
        return dfs(n);
    }

    int dfs(int n){
        if(cache[n] != 0){
            return cache[n];
        }

        int min = Integer.MAX_VALUE;
        for(int i = 1 ; i <=100 ; i ++){
            int now = i * i;
            if(n == now){
                min = 1;
                break;
            }
            if( n - now < 1 ){
                break;
            }
            min = Math.min(min , dfs(n - now) + 1);
        }

        cache[n] = min;
        return min;
    }
}
```