## Elementary algorithm dynamic programming (2)

Abbot's temple 2020-11-13 05:37:51
elementary algorithm dynamic programming

Before that Primary algorithm - Dynamic programming Another solution of dynamic programming that is less written in one article is ` Matrix solution `

Recursive problems can be expressed in a non recursive way , The time complexity is O(n), Use matrix to solve time complexity O(logn)

``````public static int climbStairs2(int n) {
if(n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
// m * n Matrix expression int[m][n]
int [][] pre = {
{1,1}, {1,0}};
int [][] result = matrixPower(pre, n-2);
return 2 * result[0][0] + result[1][0];
}
public static int[][] matrixPower(int[][] m, int p) {
int[][] result = new int[m.length][m[0].length];
for (int i =0;i< result.length; i++) {
result[i][i] =1;
}
int[][] tmp = m;
// Matrix N Power 3 = 2^0 + 2^1
for(; p != 0; p >>=1) {
if ((p&1)!=0) {
// This one is 1, Then add the product and
result =multiMatrix(result, tmp);
}
// 2 The calculation of the power , Every bit is 2^n
tmp = multiMatrix(tmp, tmp);
}
return result;
}
/**
* Matrix multiplication
* @param m1
* @param m2
* @return
*/
public static int[][] multiMatrix(int[][] m1, int[][] m2) {
int[][] result = new int [m1.length][m2[0].length];
for(int i=0;i <m2[0].length ; i++) {
for (int j = 0; j < m1.length; j++) {
for (int k =0; k< m2.length; k++) {
result[i][j] += m1[i][k] * m2[k][j];
}
}
}
return result;
}
``````