#### [70\. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/) ``` class Solution { public: int climbStairs(int n) { if (n <= 2) return n; vector<int> f(n + 1, 1); for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; } }; ``` #### [198\. 打家劫舍](https://leetcode-cn.com/problems/house-robber/) ``` class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> f(n + 1, 0); f[1] = nums[0]; for (int i = 2; i <= n; i++) { // 不偷 f[i-1] // 偷 f[i-2] + nums[i-1] // 两者取最大值 f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]); } return f[n]; } }; ``` #### [413\. 等差数列划分](https://leetcode-cn.com/problems/arithmetic-slices/) ``` class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); if (n < 3) return 0; vector<int> f(n, 0); for (int i = 2; i < n; i++) { if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) { f[i] = f[i-1] + 1; } } return accumulate(f.begin(), f.end(), 0); } }; ``` #### [542\. 01 矩阵](https://leetcode-cn.com/problems/01-matrix/) ``` class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int m = matrix.size(); int n = matrix[0].size(); vector<vector<int>> f(m, vector<int>(n, INT_MAX - 1)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { f[i][j] = 0; } else { if (i > 0) f[i][j] = min(f[i][j], f[i-1][j] + 1); // 上 if (j > 0) f[i][j] = min(f[i][j], f[i][j-1] + 1); // 左 } } } for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (matrix[i][j] != 0) { if (i < m - 1) f[i][j] = min(f[i][j], f[i+1][j] + 1); // 下 if (j < n - 1) f[i][j] = min(f[i][j], f[i][j+1] + 1); // 右 } } } return f; } }; ```