java算法学习索引之动态规划

一 斐波那契数列问题的递归和动态规划

【题目】给定整数N，返回斐波那契数列的第N项。

补充问题 1：给定整数 N，代表台阶数，一次可以跨 2个或者 1个台阶，返回有多少种走法。

【举例】N=3，可以三次都跨1个台阶；也可以先跨2个台阶，再跨1个台阶；还可以先跨1个台阶，再跨2个台阶。所以有三种走法，返回3。

补充问题 2：假设农场中成熟的母牛每年只会生 1 头小母牛，并且永远不会死。第一年农场有1只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛3年之后成熟又可以生小母牛。给定整数N，求出N年后牛的数量。

【举例】N=6，第1年1头成熟母牛记为a；第2年a生了新的小母牛，记为b，总牛数为2；第3年a生了新的小母牛，记为c，总牛数为3；第4年a生了新的小母牛，记为d，总牛数为4。第5年b成熟了，a和b分别生了新的小母牛，总牛数为6；第6年c也成熟了，a、b和c分别生了新的小母牛，总牛数为9，返回9。

【要求】对以上所有的问题，请实现时间复杂度为O（logN）的解法。

斐波那契数列问题

奶牛问题

private int[][] multiMatrix(int[][] m1, int[][] m2) {//矩阵乘法// TODO Auto-generated method stubint[][] res=new int[m1.length][m2[0].length];for (int i = 0; i < m1.length; i++) {for (int j = 0; j < m2[0].length; j++) {for (int k = 0; k < m2.length; k++) {res[i][j]+=m1[i][k]*m2[k][j];}}}return res;
}public int f3(int n)
{if (n<1) {return 0;}if (n==1||n==2) {return 1;}int [][] base= {{1,1},{1,0}};int[][] res=matrixPower(base, n-2);return res[0][0]+res[1][0];
}public int c3(int n)
{if (n<1) {return 0;}if (n==1||n==2||n==3) {return 3;}int [][] base= {{1,0,1},{0,0,1},{1,0,0}};int[][] res=matrixPower(base, n-3);return 3*res[0][0]+2*res[1][0]+res[2][0];
}

二 矩阵的最小路径和

给定一个矩阵 m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。

经典动态规划方法。假设矩阵 m的大小为 M×N，行数为 M，列数为 N。先生成大小和 m一样的矩阵dp，dp[i][j]的值表示从左上角（即（0，0））位置走到（i，j）位置的最小路径和。对m的第一行的所有位置来说，即（0，j）（0≤j<N），从（0，0）位置走到（0，j）位置只能向右走，所以（0，0）位置到（0，j）位置的路径和就是 m[0][0..j]这些值的累加结果。同理，对 m 的第一列的所有位置来说，即（i，0） （0≤i<M），从（0，0）位置走到（i，0）位置只能向下走，所以（0，0）位置到（i，0）位置的路径和就是m[0..i][0]这些值的累加结果。

除第一行和第一列的其他位置（i，j）外，都有左边位置（i-1，j）和上边位置（i，j-1）。从（0，0）到（i，j）的路径必然经过位置（i-1，j）或位置（i，j-1），所以，dp[i][j]=min{dp[i-1][j]，dp[i][j-1]}+m[i][j]，含义是比较从（0，0）位置开始，经过（i-1，j）位置最终到达（i，j）的最小路径和经过（i，j-1）位置最终到达（i，j）的最小路径之间，哪条路径的路径和更小。那么更小的路径和就是 dp[i][j]的值。

public int minPathSum1(int[][] m) {if (m==null||m.length==0||m[0]==null||m[0].length==0) {return 0;}int row=m.length;int col=m[0].length;int[][] dp=new int[row][col];dp[0][0]=m[0][0];for (int i = 1; i < row; i++) {dp[i][0]=dp[i-1][0]+m[i][0];}for (int j = 0; j < col; j++) {dp[0][j]=dp[0][j-1]+m[0][j];}for (int i = 1; i < row; i++) {for (int j = 0; j < col; j++) {dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];}}return dp[row-1][col-1];}

矩阵中一共有 M×N 个位置，每个位置都计算一次从（0，0）位置达到自己的最小路径和，计算的时候只是比较上边位置的最小路径和与左边位置的最小路径和哪个更小，所以时间复杂度为O（M×N），dp矩阵的大小为M×N，所以额外空间复杂度为O（M×N）。动态规划经过空间压缩后的方法。这道题的经典动态规划方法在经过空间压缩之后，时间复杂度依然是O（M×N），但是额外空间复杂度可以从O（M×N）减小至O（min{M，N}），也就是不使用大小为M×N的dp矩阵，而仅仅使用大小为min{M，N}的arr数组。具体过程如下

public int minPathSum2(int[][] m)
{if (m==null||m.length==0||m[0]==null||m[0].length==0) {return 0;}int more=Math.max(m.length, m[0].length);int less=Math.min(m.length, m[0].length);boolean rowmore= more==m.length;int[] arr=new int[less];arr[0]=m[0][0];for (int i = 1; i < less; i++) {arr[i]=arr[i-1]+(rowmore? m[0][i]:m[i][0]);//先求出到对角线的值}//数组  arr 中保存的是dp[i][i]中的值，但如果给定的矩阵行数小于列数（M<N），那么就生成长度为M的arr，然后令arr更新成dp矩阵每一列的值，及将arr 中的值保存为 dp[i][N]// 从左向右滚动过去for (int i = 1; i < more; i++) {arr[0]=arr[0]+(rowmore?m[i][0]:m[0][i]);for (int j = 1; j < arr.length; j++) {arr[j]=Math.min(arr[j-1], arr[j])+(rowmore?m[i][j]:m[j][i]);}}return arr[less-1];}