动态规划.md

leetcode.509 斐波那契数

• 链接https://leetcode.cn/problems/fibonacci-number/
• 解题思路：动态规划
  1. 状态表示：f[i]表示第 i 个数的斐波那契值
  2. 状态计算：f[i] = f[i-1] + f[i-2]
  3. 起始状态：由状态计算表达式可知f[2]由f[1]和f[0]推导得出，所以初始化f[0] = 0, f[1] = 1
• leetcode解题代码

class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        vector<int> f(n + 1);
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i ++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
};

leetcode.70 爬楼梯

• 链接https://leetcode.cn/problems/climbing-stairs/
• 解题思路：动态规划
  1. 状态表示：f[i]表示爬到第 i 阶楼梯有多少种方法
  2. 状态计算：第i阶楼梯可以从第 i-1 阶爬上来或从第 i-2 阶爬上来，所以f[i] = f[i-1] + f[i-2]
  3. 起始状态：楼梯从第1阶开始算起，由状态计算表达式可知f[3]由f[2]和f[1]推导得出，所以初始化f[2] = 1, f[1] = 1
• leetcode解题代码

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        
        vector<int> f(n + 1);
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i ++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
};

leetcode.746 使用最小花费爬楼梯

• 链接https://leetcode.cn/problems/min-cost-climbing-stairs/
• 解题思路：动态规划
• 注意：站在当前台阶不需要花费，只有从当前台阶向上爬才需要花费
  1. 状态表示：f[i]表示爬到第 i 阶楼梯的最低花费是多少
  2. 状态计算：
     第 i 阶楼梯可以从第 i-1 阶爬上来或从第 i-2 阶爬上来
     从第 i-1 阶爬上来的花费是f[i-1] + cost[i-1]
     从第 i-2 阶爬上来的花费是f[i-2] + cost[i-2]
     所以f[i] = min(f[i-1] + cost[i-1],f[i-2] + cost[i-2])
  3. 起始状态：由题意可知可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯楼梯从第 1 阶开始算起，由状态计算表达式可知f[2]由f[1]和f[0]推导得出，所以初始化f[0] = 0, f[1] = 0
• leetcode解题代码

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

leetcode.62 不同路径

• 链接https://leetcode.cn/problems/unique-paths/
• 解题思路：动态规划
  1. 状态表示：f[i][j]表示移动到下标为 (i, j) 的格子共有多少条不同的路径
  2. 状态计算：由于只能向下或者向右移动一步，所以 (i, j) 只能由 （i-1, j）和 (i, j-1) 得到
     所以f[i][j] = f[i - 1][j] + f[i][j - 1]
     注意状态表示是路径不是步数，所以状态计算不需要+1
  3. 起始状态：由状态计算可知，只能向下或向右更新状态，所以最上方的一行和最左边的一列均需要初始化，由于只有一条路径所以初始化为1，f[i][0] = 1, f[0][j] = 1
• leetcode解题代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m + 1, vector<int>(n + 1));

        for (int i = 0; i < m; i ++) f[i][0] = 1;
        for (int j = 0; j < n; j ++) f[0][j] = 1;
        for (int i = 1; i < m; i ++)
            for (int j = 1; j < n; j ++)
                f[i][j] = f[i - 1][j] + f[i][j - 1];
        return f[m - 1][n - 1];
    }
};

leetcode.63 不同路径Ⅱ

• 链接https://leetcode.cn/problems/unique-paths-ii/
• 解题思路：动态规划
• 注意：与上题不同之处在于
  1. 状态计算的条件：只有当前位置 (i, j) 不是障碍的时候才需要更新状态
  2. 初始化的条件：只有当前位置 (i, j) 不是障碍的时候才需要初始化为 1
  3. 如果障碍物在左上角或右下角（起始位置或终止位置），那么不存在路径直接返回 0
• leetcode解题代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) return 0;
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        
        for (int i = 0; i < n && grid[i][0] == 0; i ++)
            f[i][0] = 1;
        for (int j = 0; j < m && grid[0][j] == 0; j ++)
            f[0][j] = 1;
       
        for (int i = 1; i < n; i ++)
            for (int j = 1; j < m; j ++){
                if (grid[i][j] == 0)
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        return f[n - 1][m - 1];
                
    }
};

leetcode.64 最小路径和

• 链接https://leetcode.cn/problems/minimum-path-sum/
• 解题思路：动态规划
  1. 状态表示：f[i][j]表示移动到下标为 (i, j) 的格子路径上的数字总和为最小
  2. 状态计算：由于只能向下或者向右移动一步，所以 (i, j) 只能由 （i-1, j）和 (i, j-1) 得到
     所以f[i][j] = min(f[i - 1][j] + f[i][j - 1]) + grid[i][j]
  3. 起始状态：由状态计算可知，只能向下或向右更新状态，所以最上方的一行和最左边的一列均需要初始化
• leetcode解题代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        if (n)

        f[0][0] = grid[0][0];
        for (int i = 1; i < n; i ++)
            f[i][0] = f[i - 1][0] + grid[i][0];
        for (int j = 1; j < m; j ++)
            f[0][j] = f[0][j - 1] + grid[0][j];
        
        for (int i = 1; i < n; i ++)
            for (int j = 1; j < m; j ++)
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
        
        return f[n - 1][m - 1];
    }
};

leetcode.343 整数拆分

• 链接https://leetcode.cn/problems/integer-break/
• 解题思路：动态规划
  1. 状态表示：f[i]表示拆分正整数 i 可以获得的最大乘积
  2. 状态计算：f[i]可以拆分成 j 和 i-j，j的范围[1, i-1]
     有两种情况，i-j 不再拆分，乘积为j * (i - j)
     i-j 继续拆分，乘积为j * f[i-j]
     （为什么不拆分j呢？因为j是从1开始遍历的，f[i-j]包括了f[j]的所有情况）
     最大乘积两者取max即可
     f[i] = max(f[i], max(j * (i - j), j * f[i - j]))
  3. 起始状态：由题目可知 0 和 1 不可被拆分，所以从2开始初始化，f[2] = 1
• leetcode解题代码

class Solution {
public:
    int integerBreak(int n) {
        vector<int> f(n + 1);

        f[2] = 1;
        for (int i = 3; i <= n; i ++)
            for (int j = 1; j < i; j ++)
                f[i] = max(f[i], max(j * (i - j), j * f[i - j]));
        return f[n];
    }
};

---