---

1.下降路径最小和

1.题目链接

• 下降路径最小和

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 到达[i, j]位置时，最小的下降路径
      

  • 推导状态转移方程

    • dp[i][j] = min(x, y, z) + m[i][j]
      

  • 初始化：vector<vector<int>> dp(n + 1, vector<int>(m + 2, INT_MAX))

    • dp[0, i] = 0 -> 第一行初始化为0
      

  • 确定填表顺序：从上往下

  • 确定返回值：最后一行的最小值

---

3.代码实现

int minFallingPathSum(vector<vector<int>>& matrix) 
{
    // Init
    int n = matrix.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
    for(int i = 0; i < n + 2; i++)
    {
        dp[0][i] = 0;
    }

    // Dynamic Plan
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 1; j < n + 1; j++)
        {
            dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1]))
                + matrix[i - 1][j - 1]; 
        }
    }

    // 找最小值
    int ret = INT_MAX;
    for(int i = 0; i < n + 2; i++)
    {
        ret = min(ret, dp[n][i]);
    }

    return ret;
}

---

2.最小路径和

1.题目链接

• 最小路径和

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 走到dp[i][j]的时候，最小路径和
      

  • 推导状态转移方程

    • dp[i][j] = min(dp[i - 1][j] + dp[i][j - 1]) + g[i - 1][j - 1]

  • 初始化：dp表多开一行和一列虚拟结点，避免处理边界

    • dp[0][1] = dp[1][0] = 0
      

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

int minPathSum(vector<vector<int>>& grid) 
{
    // Init
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
    dp[0][1] = dp[1][0] = 0;

    // Dynamic Plan
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 1; j < m + 1; j++)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    return dp[n][m];
}

---

3.地下城游戏

1.题目链接

• 地下城游戏

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 从[i, j]出发，到达终点，所需的最低初始健康点数
      

  • 推导状态转移方程

    • dp[i][j] = min(dp[i][j + 1] + dp[i + 1][j]) - d[i][j]
    • dp[i][j] = max(1, dp[i][j]
      • 避免出现负血量也可以来到此位置
        

  • 初始化：vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX))

    • dp[n][m - 1] = dp[n - 1][m] = 1
      

  • 确定填表顺序：从下往上，从右往左

  • 确定返回值：dp[0][0]

• 本题为什么不可以到[i, j]…？
  • 因为本题中，[i, j]的值不仅受前面两个值影响，也受后面两个值影响
  • 如果从前面，可能确实从前面可以到[i, j]，但是从[i, j]到后面就无法进行下去了

---

3.代码实现

int calculateMinimumHP(vector<vector<int>>& d) 
{
    // Init
    int n = d.size(), m = d[0].size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
    dp[n][m - 1] = dp[n - 1][m] = 1;

    // Dynamic Plan
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = m - 1; j >= 0; j--)
        {
            dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - d[i][j];
            dp[i][j] = max(1, dp[i][j]); // 防止"死了还能到":P
        }
    }

    return dp[0][0];
}