0.动态规划与暴力递归基础
基础理论知识请参考我的算法课程学习之动态规划与暴力递归
1.线性DP
3.递推型DP
所有线性递推关系都可以用矩阵快速幂做，可以达到O(logN)，最典型是斐波那契数列。
斐波那契数列
递推公式遵守F(N) = F(N-1) + F(N-2), 对于第N项，有矩阵乘法的方式可以将时间复杂度降到O(logN)。可以用矩阵的形式，表达递推公式:
根据前四列的值，可以推导出:
多推倒几次后，可以得到如下通式:
求数列就转化成了，状态矩阵的乘法和幂运算。
矩阵乘法和幂运算
矩阵乘法，要遵守[m,n] * [n,m'], 也就是维度要匹配。新矩阵的(i,j)项是m矩阵的第i行和m'矩阵第j列的内积，所以两个矩阵的维度要匹配，不然无法在这里求内积。
public static long[][] matrixMulti(long[][] m1, long[][] m2) {
// 矩阵乘法: [m*n] * [n*m'] => m*m'
int row = m1.length;
int col = m2[0].length;
long[][] res = new long[row][col];
// 填充每一个元素
for (int i=0; i<row; i++){
for(int j=0; j<col; j++){
// res[i][j] = m1中i行的每个元素和m2中j列的每个元素，相乘并相加
for(int k=0; k<m2.length; k++){
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
} 矩阵的幂运算，就是多次乘法运算，这里先解释如何快速求10的75次方？
- 75的二进制形式是1001011
- 10的75次方=10ˆ64 * 10ˆ8 * 10ˆ2 * 10ˆ1。
在过程一中，先求出10ˆ1, 再根据它平方求出10ˆ2, 再由10ˆ2的平方求出10ˆ4,..., 75的二进制有多少位，就使用几次乘法。
在过程二中，把75对应的二进制上为1的位，累乘所得到的数相乘即可，比如10ˆ64，10ˆ8，10ˆ2， 10ˆ1应该累乘；而32，16，4上对应的累乘数，不相乘。
// temp 被 matrixMulti的结果所更新
public static long[][] matrixPower(long[][] m, long power){
// 只有方阵有幂运算，结果也是方阵
long[][] res = new long[m.length][m[0].length];
// 运算子，每次都要自乘，也就是一次幂已经计算了
long[][] temp = m;
// 先把res初始化为单位阵
for (int i=0; i<m.length; i++){
res[i][i] = 1;
}
// 一个数二进制有多少位: 右移位直到为0的移动次数
for (; power!=0; power >>= 1){
// 二进制最低位上是否为0
// 不为0，则累乘
if ( (power&1) != 0 ){
// 这里的temp是n次幂
res = matrixMulti(res, temp);// 单位矩阵的作用就类似1
}
// 更新n次幂，为下次循环做准备
temp= matrixMulti(temp, temp);
}
return res;
} 定义好了上述两个运算，求Fabonacci第N项就是，现将状态矩阵进行N-2次幂运算，再左乘初始状态矩阵[F(2), F(1)]
// 计算Fibonacci数列的第n项
public static long getFibonacciNth(long N){
// base case:
if (N == 1 || N == 2){
return 1;
}
long[][] base = { {1,1},
{1,0} };
long[][] res = matrixPower(base, N-2);
// 1*res[0][0] + 1*res[1][0];
return res[0][0] + res[1][0];
} 跳台阶(12型求方法数)
奶牛繁殖
4. 贪心策略DP
跳跃游戏2
题号45
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
请在这里输入引用内容
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
题解思路:
每走出一步中找到最远能达到边界，如果当前位置大于这个边界了，就说明我们不得不跳跃一次，每次跳跃必定是最远的那个。
// 每次尝试走一步，如果走到超出最大边界了，则步数+1，也就是被迫走的每一步都是能达到最大
// 边界的
public static int jump(int[] nums) {
// 跳的步数
int step = 0;
// 跳当前步，最远能达到的地方
int curRange = 0;
// 多跳一步，最远能达到的地方，为下一次跳做准备
int nextRange = -1;
for (int i = 0; i < nums.length; i++){
// 不得不跳一步，从之前准备好的最远的，跳那一步
if ( curRange < i){
++step;
curRange = nextRange;
}
// 比如，在i=0的位置上，跳出第一步能达到的最远距离就是 i+nums[i]
nextRange = Math.max(nextRange, i + nums[i]);
}
return step;
} 5. 计数型DP
计数型DP可以以组合数学的方法写出组合数，然后dp求组合数，比如“不同路径I”
不同路径
Nr. 62
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
请在这里输入引用内容
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
解题思路:
创建DP数组，dp[i][j]表示到达(i,j)的方法数，它是由子问题dp[i-1][j]和dp[i][j-1]
注意初始化条件，第一行和第一列都是1，方法数都是1，因为只能直行。
// dp[i][j] 就表示到达(i,j)位置的方法数，它是由子问题，左边和上边的方法数
public static int uniquePaths_DP(int m, int n){
// 棋盘其实是 n*m
int[][] dp = new int[n][m];
int rows = dp.length;
int cols = dp[0].length;
// base case: 因为只能向下或者向右，所以第一行，第一列的值都是1，只有一种走法
// 第一行
for (int i = 0; i < m; i++){
dp[0][i] = 1;
}
for (int i = 0; i < n; i++){
dp[i][0] = 1;
}
for (int i=1; i<rows; i++){
for (int j=1; j<cols; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
// 想求board[n-1][m-1]的值
return dp[rows-1][cols-1];
} 这种依赖左边和上边的可以空间压缩成一个数组。
public static int uniquePaths_DP3(int m, int n){
int[] dp = new int[m];
int len = m;
// 空间压缩
Arrays.fill(dp, 1);
for (int row=1; row<n; row++){
for (int i=1; i<m; i++){
// In-place 修改空间压缩
// 等号右边的 dp[i]表示上一次的结果，也就是二维中上面的结果
// 等号右边的 dp[i-1]表示左边的结果，也就是二维中左面的结果
dp[i] = dp[i] + dp[i-1];
}
}
return dp[m-1];
} 不同路径II
Nr. 63
一一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
请在这里输入引用内容
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
请在这里输入引用内容
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
解题思路：
和62类似，也是建立DP数组，不过要注意边界条件。第一行和第一列如果遇到障碍物，后面的格子都不可达，所以都是0。如果(i,j)不是障碍物，则dp[i][j]的公式和62一致。
public static int getPaths_DP(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length==0){
return 0;
}
int rows = obstacleGrid.length;
int cols = obstacleGrid[0].length;
// 初始化为0
int[][] dp = new int[rows][cols];
// 第一列中，如果不是障碍物有一种方法达到
// 一旦遇到障碍物后，后续的点都不可到达都为0
for (int i=0; i<rows && obstacleGrid[i][0] == 0; i++){
dp[i][0] = 1;
}
// 第一行中, 如果不是障碍物有一种方法达到
// 一旦遇到障碍物后，后续的点都不可到达都为0
for (int i=0; i<cols && obstacleGrid[0][i] == 0; i++){
dp[0][i] = 1;
}
// general case
for (int i=1; i<rows; i++){
for (int j=1; j<cols; j++){
// 判断是否是障碍物，是障碍物自动置0
if (obstacleGrid[i][j] == 0){
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
return dp[rows-1][cols-1];
} 这个空间优化，一定注意边界条件，也就是每次row循环时的第一个数！
并且要先处理第一行。循环从第二行开始。
public static int getPaths_DP2(int[][] obstacleGrid){
if (obstacleGrid == null || obstacleGrid.length==0){
return 0;
}
int rows = obstacleGrid.length;
int cols = obstacleGrid[0].length;
int[] dp = new int[cols];
// 第一行中, 如果不是障碍物有一种方法达到
// 一旦遇到障碍物后，后续的点都不可到达都为0
for (int i=0; i<cols && obstacleGrid[0][i] == 0; i++){
dp[i] = 1;
}
// general case
for (int i=1; i<rows; i++){
// 单独处理第一个节点
// 当上一个是0 或者 当前位置是障碍物，那么第一个位置就是0
dp[0] = (dp[0]==0 || obstacleGrid[i][0] == 1) ? 0 : 1;
for (int j=1; j<cols; j++){
// 如果当前j=0是障碍物，就要手动置零，二维方法中初始化为0
if (obstacleGrid[i][j] == 1){
dp[j] = 0;
//continue;
}else { // 如果不是障碍物，继承上一个0位置的值
dp[j] += dp[j-1];
}
}
}
return dp[cols-1];
} 
京公网安备 11010502036488号