Mark's blogs

动态规划

此处使用动态规划求解，首先需要确定的是问题的划分，对于整数 n 拆分的方式存在多种 1+n-1 或 2+n-2 ，同时也可以进一步对 n-1 和 n-2 进行拆分，此处使用一个动态规划数组 dp[i] 来表示，将数字 i 拆分为任意份后能够得到的最大乘积，那么对于数字 n 的拆分为 和 的情形最大乘积求解存在三种情况：

1. 两个值都拆分的情形 在此基础上将 和 进一步拆分为多个值的最大值 。

2. 两个值都不进行拆分的情况： 两个值都不进行拆分，那么

3. 两个值一个拆分，另一个不拆分： 对 进行拆分 $n^3_{最大乘积}=dp[n-i]iin^4_{最大乘积}=(n-i)dp[i]$

在此基础上得到递推公式为：

其中

动态规划

此处相较于62.不同路径的不同之处在于网格中存在障碍物，那么在进行动态规划数组的推导时，将会存在不同之处，也对网格中值为 0 的元素，依旧就是可以从上方和左方到达： dp[i][j]=dp[i-1][j]+dp[i][j-1] ，对于网格中值为 1 的位置应该将其置为不可达的状态： dp[i][j]=0 。相应的，动态规划数组在初始化是也存在不同。

1. 确定动态规划数组： dp[i][j] 表示从起点 [0][0] 到达 [i][j] 存在的路径数。

2. 动态规划数组的推导方式： 首先判断 obstacleGrid[i][j]==0? 若是成立，那么 dp[i][j]=dp[i-1][j]+dp[i][j-1] ，不成立那么 dp[i][j]=0 。

3. 动态规划数组的初始化：依旧是对第一行和第一列进行初始化，在第一行中 dp[0][0]=1 接下来判断 obstacleGrid[0][j]==0? ，若是成立，那么 dp[0][j]=1 ，否则 dp[0][j]=0 并且后续的 dp[0][j] 也全部为0。对于第一列的初始化：判断 obstacleGrid[i][0]==0? ，若是成立，那么 dp[i][0]=1 ，否则 dp[i][0]=0 并且后续的 dp[i][0] 也全部初始化为0。

4. 数组的遍历顺序：采取从前向后，逐行遍历的方式

5. 举例验证：obstacleGrid = [[0,1],[0,0]] 那么初始为 dp[0][0]=1,dp[0][1]=0,dp[1][0]=1 计算 dp[1][1]=dp[0][1]+dp[1][0]=1 验证正确

动态规划

1. 确定动态规划数组的含义：定义二维动态规划数组 dp[i][j] 表示到达途中 i,j 位置处存在几条路径

2. 确定递推关系：由于在题中规定只能向下和向右移动，那么对于位置 i，j 存在着两中到达的方式，第一种是从上方 i-1,j 向下一步，第二种是从左边 i,j-1 向右一步到达。那么 dp[i][j]=dp[i-1][j]+dp[i][j-1]

3. 动态规划数组的初始化：首先是 dp[0][0] 也就是起点，那么只有一条路径，初始化为 dp[0][0]=1 ，对于 dp[i][0] 也就是最左边一列的元素，只能从起点处不断向下走 dp[i][0]=1 ，同理最上方一行 dp[0][i]=1 。

4. 遍历方式：采取逐行或者逐列遍历的方式都是可行的。

5. 举例说明： m = 3, n = 2 ，首先完成初始化：dp[0][0]=0,dp[1][0]=1,dp[2][0]=1,dp[0][1]=1 再基础上逐行进行推导：第2行 dp[1][1]=dp[0][1]+dp[1][0]=2 在此基础上推导第三行： dp[2][1]=dp[1][1]+dp[2][0]=3 验证正确。

动态规划

1. 确定dp数组（dp table）以及下标的含义：使用 dp[i] 作为动态规划数组，表示到达阶梯 i 的最小花费

2. 确定递推公式：对于要到达第 i 个楼梯，存在两种方案，第一种是从 i-1 向前一步，或者从 i-2 向前两步，对应的递推公式为： dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3. dp数组如何初始化：对于 dp[0] 应该初始化为0，对于 dp[1] 也可以选择从1开始走，也初始化为0。

4. 确定遍历顺序：此处需要求解的是 dp[n+1] ，显而易见是从前向后遍历

5. 举例推导dp数组：对于 cost = [10,15,20] 那么 dp[2]=min(0+15,0+10)=10 , dp[3]=min(10+20,0+15)=15 验证成立

并且此处当前状态的决策只和前两个状态有关，因此可以在常数空间复杂度内实现。

动态规划

1. 动态规划数组的下标及含义： dp[i] 表示总计 i 个楼梯的爬楼方式，总计的长度为n

2. 递推公式： dp[i]=dp[i-1]+dp[i-2] ，此处的理解可以使当前剩余 i 阶楼梯，当前这一步分别走一步或者两步。

3. dp数组的初始化：当 i=1 时，明显不存在方法 dp[1]=1 ，当 i=2 时，只能走一步 dp[2]=2

4. 遍历顺序：此处需要求解的是 dp[n] 那么明显需要从前向后进行递推

5. 举例推导：n=3 dp[3]=dp[1]+dp[2]=3 满足要求

此处在初始化时，有一个较为重要的细节，就是对于 dp[0] 的定义和初始化，从 dp 数组的定义来看，此处的 dp[0] 应该代表的是，总计0个阶梯有几种爬法，那么应该是不存在爬得方式，应该是初始化为0，但是如果使用 dp[0],dp[1] 去计算 dp[2] 将会得到错误的结果，因此此处不应该初始化 dp[0] 将 dp[1],dp[2] 作为初始值去计算。

根据此处的递推公式：当前状态 i 的决策，也只和前两个状态有关，那么只需要保存前两个状态的值，实现空间复杂度的化简。

动态规划

此处已经给定了相应的状态转移方程，当前的决策是和前两个状态相关的，那么就需要从前向后递推。使用动态规划求解的步骤如下：

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

1.确定dp数组以及下标的含义

dp[i] 的定义为：第i个数的斐波那契数值是 dp[i] 由于在计算时只需要使用到前两个状态，那么在就只需要保存前两个序列即可。

2.确定递推公式

状态转移方程 dp[i] = dp[i - 1] + dp[i - 2] ;

3.dp数组如何初始化

1
2

dp[0] = 0;
dp[1] = 1;

1.1 DFS实现

此处的轴对称问题，重点在于要明白如何进行比较，对于两个子树，首先是对比子树的根节点是否相等，接下来的对比过程应该是对比左边的左孩子和右边的右孩子是否相等，然后再左右交换。重点是在于明白对比的过程，然后就能否简单的基于递归实现。

本质上就是给定一个 $9\times9$ 的二维矩阵，使用1-9对该二维矩阵进行补全。在补全矩阵后需要保证，在矩阵的每一行每一列中都不存在重复元素。并且在9个 $3\times3$ 的小方框中不存在重复的元素。并且这样的求解有且仅有一个。

采取逐行放置的方式：设计一个递归地回溯函数 bool backtrack(int row,int col,vector<vector<char>>& board) ，向函数传递的参数值为 row 行号和 col 列号，每一次仅填写 board[row][col] 位置处的元素，返回值为bool类型，表示本地递归是否找到了可行的解。首先判断 board[row][col] 位置处的元素是否是 . 若不是，则直接 col+1 向下递归，并且直接返回递归函数的返回值。

若是则使用一个hash used[9] 记录，在 board[row][col] 处那些元素是使用过的。首先是按行列进行统计，再按 $3\times3$ 的宫格进行统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

bool used[9]={false};
for(int i=0;i<board[row].size();i++){ // 处理行
    if(board[row][i]!='.') used[board[row][i]-'1']=true;
}
for(int i=0;i<board.size();i++){ // 处理列
    if(board[i][col]!='.') used[board[i][col]-'1']=true;
}
// 处理粗线宫格
for(int i=row/3*3;i<row/3*3+3;i++){
    for(int j=col/3*3;j<col/3*3+3;j++){
        if(board[i][j]!='.')
            used[board[i][j]-'1']=true;
    }
}

双hash+回溯递归

此处采取逐行去填充元素位置的方式：

1. bool col[9]={false}; 记录那些列被使用了，通过记录和逐行填充的方式实现了行列的不冲突
2. vector<pair<int,int>> pos; 记录每一行所使用的列号用于判断是否会出现的在同一斜线上

基本的递归流程：递归的参数为 n,cur 分表表示皇后的个数和当前处理的行数（从0开始），那么当 cur==n 时递归结束，将本次递归的结果集加入到结果集中。 cur 行放置位置的选取，从0开始逐个判断，是否和前面已选元素在同行和同列，或者在一条斜线上，不是则选取后递归，递归返回后再进行回溯。

是否在同一斜线上的判断：利用 pos 数组进行判断，主要是看二维坐标中的点，行距和列距是否相同。

1
2
3
4
5
6
7

bool isSlash(int i,int j){ // 第i行，第j列处的元素是否和前面的元素处于同一斜线
        if(pos.empty()) return false;
        for(auto &a:pos){
            if(abs(a.first-i)==abs(a.second-j)) return true;
        }
        return false;
    }

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。