蓝桥杯练习题——dp

五部曲（代码随想录）

1.确定 dp 数组以及下标含义

2.确定递推公式

3.确定 dp 数组初始化

4.确定遍历顺序

5.debug

入门题

1.斐波那契数

思路

1.f[i]：第 i 个数的值

2.f[i] = f[i - 1] + f[i - 2]

3.f[0] = 0, f[1] = 1

4.顺序遍历

5.记得特判 n == 0 的时候，因为初始化了 f[1]

class Solution {
public:
    int fib(int n) {
        if(n == 0) return n;
        vector f(n + 1);
        f[0] = 0, f[1] = 1;
        for(int i = 2; i 
public:
    int climbStairs(int n) {
        vector
public:
    int minCostClimbingStairs(vector
        int n = cost.size();
        vector
            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }
        return f[n];
    }
};

public:
    int uniquePaths(int m, int n) {
        vector
            for(int j = 2; j 
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[n][m];
    }
};

public:
    int uniquePathsWithObstacles(vector
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        vector
            for(int j = 1; j