做淘口令的网站,建筑企业招聘信息,四川华海建设集团有限公司网站,郑州服装网站建设公司输入#xff1a;台阶数量n 输出#xff1a;有多少种走法 规则#xff1a;每次可以上一个台阶或者两个台阶 分析#xff1a;想明白一件事情。如果现在在第k个台阶#xff0c;那下一步可以到达第k1个台阶#xff0c;或者第k2个台阶。换句话说想要到达第k个台阶#xff0c;…输入台阶数量n 输出有多少种走法 规则每次可以上一个台阶或者两个台阶 分析想明白一件事情。如果现在在第k个台阶那下一步可以到达第k1个台阶或者第k2个台阶。换句话说想要到达第k个台阶可以通过第k-1或者第k-2个台阶达到。所以第k个台阶的走法第k-1个台阶的走法第k-2个台阶的走法。
再用比较小的数检测一下对不对。 如果有1个台阶有1种走法1。 如果有2个台阶有2种走法112。 如果有3个台阶可以从第2个台阶再走1个到达3也可以从第1个台阶再走2个到达3。所以nums[3]nums[2]nums[1]213。实际上也是1112112。 如果有4个台阶可以从第3个台阶再走1个到达4也可以从第2个台阶再走2个到达4。所以nums[4]nums[3]nums[2]325。实际走法1111211121从第3个台阶 11222从第2个台阶 验证正确。可以编码了。
以下代码从回溯、备忘录模式、动态规划、节省空间版的动态规划。不做详细介绍直接看代码。
/*** 暴力* param n* return*/public int climbStairs(int n) {if(n0) return 0;if(n1) return 1;if(n2) return 2;return climbStairs(n-1)climbStairs(n-2);}/*** 备忘录模式* param n* return*/public int climbStairsV2(int n) {int[] memo new int[n1];climbStairs(n,memo);return memo[n];}private int climbStairs(int n,int[] memo){if(n0) return 0;if(memo[n]0) return memo[n];if(n2){memo[n]n;return memo[n];}memo[n] climbStairs(n-1,memo)climbStairs(n-2,memo);return memo[n];}/*** 动态规划自底向上* param n* return*/public int climbStairsV3(int n) {if(n1) return 1;int[] dp new int[n1];dp[1]1;dp[2]2;for(int i3;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}/*** 节省内存的动态规划但实际LeetCode反馈出来的内存并不少* param n* return*/public int climbStairsV4(int n) {if(n1) return 1;int num1 1;int num2 2;int num30;for(int i3;in;i){num3num1num2;num1num2;num2num3;}return num2;}还有第五种解法利用矩阵乘法。先看菲波那切数列中011258… 我们利用以下公式 [FnFn−1Fn−1Fn−2][1110]n−1\left[ \begin{matrix} F_{n} amp; F_{n-1} \\ F_{n-1} amp; F_{n-2} \end{matrix} \right] \left[ \begin{matrix} 1 amp; 1 \\ 1 amp; 0 \end{matrix} \right] ^{n-1}[FnFn−1Fn−1Fn−2][1110]n−1 可以求得第n个斐波那契数列的值。使用数学归纳法证明。 我们当前题目与斐波那契数列的不同是起始值不同我们的序列是01235813…所以我们求第n个值使用的公式是
[FnFn−1Fn−1Fn−2][2110]∗[1110]n−2(ngt;1)\left[ \begin{matrix} F_{n} amp; F_{n-1} \\ F_{n-1} amp; F_{n-2} \end{matrix} \right] \left[ \begin{matrix} 2 amp; 1 \\ 1 amp; 0 \end{matrix} \right]*\left[ \begin{matrix} 1 amp; 1 \\ 1 amp; 0 \end{matrix} \right] ^{n-2}(ngt;1)[FnFn−1Fn−1Fn−2][2110]∗[1110]n−2(n1)
我们看到两个公式不一样的地方是初始化值不同。
public int climbStairsV5(int n) {if(n2) return n;int[][] q {{1,1},{1,0}};int[][] p {{2,1},{1,0}};int[][] res pow(q,n-2);res multiply(p,res);return res[0][0];}private int[][] pow(int[][] a,int n){if(n1){return a;}a pow(a,n/2);a multiply(a,a);if(n%2!0){int[][] ret {{1,1},{1,0}};a multiply(ret,a);}return a;}private int[][] multiply(int[][] a, int[][] b) {int[][] c new int[2][2];c[0][0] a[0][0]*b[0][0]a[0][1]*b[1][0];c[0][1] a[0][0]*b[0][1] a[0][1]*b[1][1];c[1][0] a[1][0] * b[0][0]a[1][1]*b[1][0];c[1][1] a[1][0]*b[0][1]a[1][1]*b[1][1];return c;}代码添加链接描述
