本文共 1856 字，大约阅读时间需要 6 分钟。

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

思路： ①动态规划 时间复杂度：O(n) 空间复杂度：O(1)

int fib(int n) {
       if (n < 2) {
           return n;    }    int p = 0, q = 0, r = 1;    for (int i = 2; i <= n; ++i) {
           p = q;        q = r;        r = p + q;    }    return r;}

②矩阵快速幂

时间复杂度：O(logn)。 空间复杂度：O(1) 代码：略 ③通项公式 复杂度：代码中使用的 \texttt{pow}pow 函数的时空复杂度与 CPU 支持的指令集相关，这里不深入分析。 代码：

int fib(int n) {
       double sqrt5 = sqrt(5);    double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);    return round(fibN / sqrt5);}

注解：

sqrt()用来计算平方根 pow(): C 库函数 double pow(double x, double y) 返回 x 的 y 次幂 round(x):返回x的四舍五入整数值

2.矩阵的最小路径和

题目：

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

举例：

示例 1： 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 示例 2： 输入：grid = [[1,2,3],[4,5,6]] 输出：12

int minPathSum(int** grid, int gridSize, int* gridColSize){
       int i,j;    if(gridSize==0|| *gridColSize==0){
           return 0;    }    int dp[gridSize][*gridColSize];//gridsize为行，gridColdSize为列    dp[0][0]=grid[0][0];//初始化第一步    for(i=1;i

3.不同路径Ⅱ leetcode63

题目： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

思路：

①这样自底向上的递归会存在大量的重复计算，所以我们将其改写为在二维数组中自顶向下的递推即可，即 dp[i, j] = dp[i - 1, j] + dp[i, j - 1]dp[i,j]=dp[i−1,j]+dp[i,j−1]。

代码：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
       //获取输入数组的长和宽    int n=obstacleGridSize;//行    int m=obstacleGridColSize[0];//列        //使用滚动数组对空间复杂度进行优化,只需要知道前一列的数即可    int f[m];    //bzero(f,sizeof(int)*m);    memset(f,0,sizeof(f));    //判断开头是有石头还是可以通过    f[0]=(obstacleGrid[0][0]==0);    //先遍历整个数组    for(int i=0;i
   
    =0&&obstacleGrid[i][j-1]==0){
   //j-1>=0表示表格不在上边框没超出界限，且当前位置没石头                f[j]+=f[j-1];            }        }    }    return f[m-1];//最后返回滚动数组的最后一位}