[Day11] 2022-3-11 70. 爬楼梯

[Day11] 2022-3-11 70. 爬楼梯

前言

题目这么简单，为什么还要做，思考

递归 递归回溯和动态规划直接的的区别 和使用场景，从时间复杂度考虑

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

阅读book：Algorithms-JeffE-BW 了解时间复杂度的计算过程。

递归 递归回溯和动态规划直接的的区别？

✅ 子问题：快速排序时间复杂度怎么计算的。

✅：子问题：快速排序和归并排序的时间复杂度分析——通俗易懂

✅ 子问题：https://www.runoob.com/w3cnote/merge-sort.html 阅读完成。2个细节 合并 然后放回去。left

输出：不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

为什么超时，最坏时间复杂度是多少

• 大量重复的计算。

• 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

归并排序的性能不受输入数据的影响， 但表现比选择排序好的多， 因为始终都是 O(nlogn) 的时间复杂度。 代价是需要额外的内存空间。

package main

import (
 "fmt"
 "sort"
)

func MergeSort(list []int) []int {
 var length = len(list)
 if length < 2 {
  return list
 }
 var mid = length / 2
 return merge(MergeSort(list[:mid]), MergeSort(list[mid:]))
}

func merge(x, y []int) []int {
 var r []int = make([]int, len(x)+len(y))
 for i, j := 0, 0; ; {
  if i < len(x) && (j == len(y) || x[i] < y[j]) {
   r[i+j] = x[i]
   i++
  } else if j < len(y) {
   r[i+j] = y[j]
   j++
  } else {
   break
  }
 }
 return r
}

func main() {
 var list []int = []int{56, 48, 58, 94, 87, 4, 5, 61, 5, 8, 74, 9, 84, 15, 94, 9, 4, 31, 41, 68, 7, 4, 6, 94, 16, 9, 8, 4}
 fmt.Println(MergeSort(list))
 fmt.Println(list)

 sort.Ints(list)
 fmt.Println(list)
}

阅读：https://www.runoob.com/w3cnote/merge-sort.html 完成

阅读

阅读book：Algorithms-JeffE-BW 了解时间复杂度的计算过程。

递归 递归回溯和动态规划直接的的区别？

子问题：快速排序时间复杂度怎么计算的。

子问题：快速排序和归并排序的时间复杂度分析——通俗易懂

阅读：https://www.runoob.com/w3cnote/merge-sort.html 完成 输出：

• 代码阅读完成. int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间

private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
            //合并不递归，递归的是sort
        }
    }

https://www.runoob.com/w3cnote/quick-sort.html

动态规划 ：时间复杂度 o（n）

class Solution {
public:
    int climbStairs(int n) {

        //1 <= n <= 45
        if (1 == n) return 1;

        vector<int> dp(n+1,0); //dp[i]= 你有多少种不同的方法可以爬到楼顶呢
        dp[1] =1;
        dp[2] =2; 

        for( int i=3;i<=n;i++)
        {
            dp[i] =dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};