动态规划——粉刷房子

**动态规划——粉刷房子**

在计算机科学中，动态规划是一种常见的算法设计技术。它通过分解问题、建立状态转移方程以及使用记忆化来解决复杂的问题。在本文中，我们将使用一个实例——粉刷房子——来演示动态规划的应用。

**问题描述**

假设我们有一个长方形的房子，需要粉刷。房子的宽度为 `n` 个单位，高度为 `m` 个单位。每个单位的成本为 `c[i][j]`，其中 `i` 和 `j` 分别表示宽度和高度的坐标。

我们希望找到一种最优的粉刷方案，使得总成本最小。

**动态规划解决方案**

为了解决这个问题，我们可以使用动态规划。首先，我们需要定义状态转移方程。

假设 `dp[i][j]` 表示从左上角 `(0,0)` 到右下角 `(i, j)` 的最优粉刷方案的成本。

我们可以通过以下方式更新 `dp[i][j]`：

* 如果 `i ==0` 或 `j ==0`，则 `dp[i][j] = c[0][0]`
* 否则，我们有两种选择：
+ 粉刷第一行（宽度为 `i-1`），然后粉刷剩余部分（高度为 `j`）：`dp[i][j] = dp[i-1][j] + c[i][j]`
+ 粉刷第一列（高度为 `j-1`），然后粉刷剩余部分（宽度为 `i`）：`dp[i][j] = dp[i][j-1] + c[i][j]`

因此，我们可以更新状态转移方程：

def min_cost(n, m, c):
 # 初始化 dp 数组 dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

 # 填充第一行和第一列 for i in range(1, n+1):
 dp[i][0] = c[i-1][0]
 for j in range(1, m+1):
 dp[0][j] = c[0][j-1]

 # 填充剩余部分 for i in range(1, n+1):
 for j in range(1, m+1):
 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + c[i-1][j-1]

 # 返回最终答案 return dp[n][m]

n =3m =4c = [[1,5,8,9], [6,7,4,2], [3,9,1,6]]

print(min_cost(n, m, c)) # 输出：13