建大型网站公司,网站的内部推广的方法,成都市建设厅网站,ps专门做兼职的网站一 斐波那契数列问题的递归和动态规划
【题目】给定整数N#xff0c;返回斐波那契数列的第N项。
补充问题 1#xff1a;给定整数 N#xff0c;代表台阶数#xff0c;一次可以跨 2个或者 1个台阶#xff0c;返回有多少种走法。
【举例】N3#xff0c;可以三次都跨1个台…一 斐波那契数列问题的递归和动态规划
【题目】给定整数N返回斐波那契数列的第N项。
补充问题 1给定整数 N代表台阶数一次可以跨 2个或者 1个台阶返回有多少种走法。
【举例】N3可以三次都跨1个台阶也可以先跨2个台阶再跨1个台阶还可以先跨1个台阶再跨2个台阶。所以有三种走法返回3。
补充问题 2假设农场中成熟的母牛每年只会生 1 头小母牛并且永远不会死。第一年农场有1只成熟的母牛从第二年开始母牛开始生小母牛。每只小母牛3年之后成熟又可以生小母牛。给定整数N求出N年后牛的数量。
【举例】N6第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。
【要求】对以上所有的问题请实现时间复杂度为OlogN的解法。
斐波那契数列问题 奶牛问题 private int[][] multiMatrix(int[][] m1, int[][] m2) {//矩阵乘法// TODO Auto-generated method stubint[][] resnew 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 (n1) {return 0;}if (n1||n2) {return 1;}int [][] base {{1,1},{1,0}};int[][] resmatrixPower(base, n-2);return res[0][0]res[1][0];
}public int c3(int n)
{if (n1) {return 0;}if (n1||n2||n3) {return 3;}int [][] base {{1,0,1},{0,0,1},{1,0,0}};int[][] resmatrixPower(base, n-3);return 3*res[0][0]2*res[1][0]res[2][0];
} 二 矩阵的最小路径和
给定一个矩阵 m从左上角开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和返回所有的路径中最小的路径和。 经典动态规划方法。假设矩阵 m的大小为 M×N行数为 M列数为 N。先生成大小和 m一样的矩阵dpdp[i][j]的值表示从左上角即00位置走到ij位置的最小路径和。对m的第一行的所有位置来说即0j0≤jN从00位置走到0j位置只能向右走所以00位置到0j位置的路径和就是 m[0][0..j]这些值的累加结果。同理对 m 的第一列的所有位置来说即i0 0≤iM从00位置走到i0位置只能向下走所以00位置到i0位置的路径和就是m[0..i][0]这些值的累加结果。
除第一行和第一列的其他位置ij外都有左边位置i-1j和上边位置ij-1。从00到ij的路径必然经过位置i-1j或位置ij-1所以dp[i][j]min{dp[i-1][j]dp[i][j-1]}m[i][j]含义是比较从00位置开始经过i-1j位置最终到达ij的最小路径和经过ij-1位置最终到达ij的最小路径之间哪条路径的路径和更小。那么更小的路径和就是 dp[i][j]的值。
public int minPathSum1(int[][] m) {if (mnull||m.length0||m[0]null||m[0].length0) {return 0;}int rowm.length;int colm[0].length;int[][] dpnew 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 个位置每个位置都计算一次从00位置达到自己的最小路径和计算的时候只是比较上边位置的最小路径和与左边位置的最小路径和哪个更小所以时间复杂度为OM×Ndp矩阵的大小为M×N所以额外空间复杂度为OM×N。动态规划经过空间压缩后的方法。这道题的经典动态规划方法在经过空间压缩之后时间复杂度依然是OM×N但是额外空间复杂度可以从OM×N减小至Omin{MN}也就是不使用大小为M×N的dp矩阵而仅仅使用大小为min{MN}的arr数组。具体过程如下
public int minPathSum2(int[][] m)
{if (mnull||m.length0||m[0]null||m[0].length0) {return 0;}int moreMath.max(m.length, m[0].length);int lessMath.min(m.length, m[0].length);boolean rowmore morem.length;int[] arrnew 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]中的值但如果给定的矩阵行数小于列数MN那么就生成长度为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];}
