import unittestfrom typing import Listclass Solution: def minPathSum(self, grid: List[List[int]]) -> int: """ 使用动态规划计算从网格左上角到右下角的最小路径和 参数: grid: 二维整数列表，表示m x n网格 返回: int: 最小路径和 """ if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) # 初始化第一行：只能从左边来 for j in range(1, n): grid[0][j] += grid[0][j-1] # 初始化第一列：只能从上边来 for i in range(1, m): grid[i][0] += grid[i-1][0] # 填充剩余网格：取上方和左方的最小值加上当前值 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]class TestMinPathSum(unittest.TestCase): """测试最小路径和算法""" def test_leetcode_examples(self): """测试LeetCode官方示例""" solution = Solution() # 示例1: [[1,3,1],[1,5,1],[4,2,1]] -> 7 grid1 = [[1,3,1], [1,5,1], [4,2,1]] self.assertEqual(solution.minPathSum(grid1), 7) # 示例2: [[1,2,3],[4,5,6]] -> 12 grid2 = [[1,2,3], [4,5,6]] self.assertEqual(solution.minPathSum(grid2), 12) def test_single_element(self): """测试单元素网格""" solution = Solution() self.assertEqual(solution.minPathSum([[5]]), 5) self.assertEqual(solution.minPathSum([[0]]), 0) self.assertEqual(solution.minPathSum([[10]]), 10) def test_single_row(self): """测试单行网格""" solution = Solution() self.assertEqual(solution.minPathSum([[1, 2, 3]]), 6) # 1+2+3=6 self.assertEqual(solution.minPathSum([[5, 1, 3]]), 9) # 5+1+3=9 self.assertEqual(solution.minPathSum([[0, 0, 0]]), 0) # 全零 def test_single_column(self): """测试单列网格""" solution = Solution() self.assertEqual(solution.minPathSum([[1], [2], [3]]), 6) # 1+2+3=6 self.assertEqual(solution.minPathSum([[5], [1], [3]]), 9) # 5+1+3=9 self.assertEqual(solution.minPathSum([[0], [0], [0]]), 0) # 全零 def test_2x2_grid(self): """测试2x2网格""" solution = Solution() self.assertEqual(solution.minPathSum([[1, 2], [3, 4]]), 7) # 1+2+4=7 或 1+3+4=7 self.assertEqual(solution.minPathSum([[1, 3], [2, 1]]), 4) # 1+2+1=4 def test_3x3_grid(self): """测试3x3网格""" solution = Solution() grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] self.assertEqual(solution.minPathSum(grid), 21) # 1+2+3+6+9=21 def test_rectangular_grids(self): """测试矩形网格""" solution = Solution() # 4x2网格 grid1 = [[1, 2], [3, 4], [5, 6], [7, 8]] self.assertEqual(solution.minPathSum(grid1), 24) # 1+2+4+6+8=21? 需要验证 # 2x4网格 grid2 = [[1, 2, 3, 4], [5, 6, 7, 8]] self.assertEqual(solution.minPathSum(grid2), 24) # 1+2+3+4+8=18? 需要验证 def test_with_zeros(self): """测试包含零的网格""" solution = Solution() # 网格中包含零 grid1 = [[0, 1], [1, 0]] self.assertEqual(solution.minPathSum(grid1), 1) # 0+1+0=1 或 0+1+0=1 # 第一行有零 grid2 = [[0, 0, 1], [1, 1, 1]] self.assertEqual(solution.minPathSum(grid2), 2) # 0+0+1+1=2 def test_minimum_values(self): """测试最小值边界""" solution = Solution() self.assertEqual(solution.minPathSum([[0]]), 0) self.assertEqual(solution.minPathSum([[1]]), 1) def test_all_same_values(self): """测试所有元素相同的网格""" solution = Solution() # 全1网格 grid1 = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] self.assertEqual(solution.minPathSum(grid1), 5) # 需要向右2次向下2次：1+1+1+1+1=5 # 全5网格 grid2 = [[5, 5], [5, 5]] self.assertEqual(solution.minPathSum(grid2), 15) # 5+5+5=15 def test_algorithm_correctness(self): """验证算法正确性（多种情况对比）""" solution = Solution() test_cases = [ # (grid, expected, description) ([[1,3,1],[1,5,1],[4,2,1]], 7, "LeetCode示例1"), ([[1,2,3],[4,5,6]], 12, "LeetCode示例2"), ([[5]], 5, "单元素"), ([[1,2,3]], 6, "单行"), ([[1],[2],[3]], 6, "单列"), ([[1,2],[3,4]], 7, "2x2网格"), ] for grid, expected, description in test_cases: with self.subTest(description=description): # 创建网格的副本，避免测试间相互影响 import copy grid_copy = copy.deepcopy(grid) actual = solution.minPathSum(grid_copy) self.assertEqual(actual, expected)class TestMinPathSumEdgeCases(unittest.TestCase): """测试边界情况""" def test_empty_grid(self): """测试空网格""" solution = Solution() self.assertEqual(solution.minPathSum([]), 0) self.assertEqual(solution.minPathSum([[]]), 0) def test_large_grid(self): """测试较大网格（性能验证）""" solution = Solution() # 创建较大的网格（但仍在小范围内） large_grid = [[1] * 10 for _ in range(10)] # 10x10全1网格，最小路径和 = 1 + (10-1) + (10-1) = 19 result = solution.minPathSum(large_grid) self.assertEqual(result, 19) def test_path_selection(self): """测试路径选择逻辑""" solution = Solution() # 这个网格中，向下比向右更优 grid = [[1, 100], [2, 1], [1, 1]] # 最优路径：1→2→1→1 = 5，而不是1→100→1 = 102 self.assertEqual(solution.minPathSum(grid), 5)def run_comprehensive_tests(): """运行全面测试并生成详细报告""" # 创建测试加载器 loader = unittest.TestLoader() # 创建测试套件 suite = unittest.TestSuite() suite.addTests(loader.loadTestsFromTestCase(TestMinPathSum)) suite.addTests(loader.loadTestsFromTestCase(TestMinPathSumEdgeCases)) # 运行测试 runner = unittest.TextTestRunner(verbosity=2) result = runner.run(suite) # 生成测试报告 print("\n" + "="*60) print("最小路径和算法测试报告") print("="*60) print(f"运行测试数: {result.testsRun}") print(f"失败数: {len(result.failures)}") print(f"错误数: {len(result.errors)}") if result.wasSuccessful(): print("🎉 所有测试通过！算法实现正确。") # 显示关键测试用例验证 print("\n关键测试用例验证:") solution = Solution() key_test_cases = [ ([[1,3,1],[1,5,1],[4,2,1]], 7, "LeetCode示例1"), ([[1,2,3],[4,5,6]], 12, "LeetCode示例2"), ([[5]], 5, "单元素网格"), ([[1,2,3]], 6, "单行网格"), ] for grid, expected, description in key_test_cases: actual = solution.minPathSum(grid) status = "✅" if actual == expected else "❌" print(f"{description:12} | 输入: {grid}") print(f"{'':12} | 输出: {actual} (期望: {expected}) {status}") print("-" * 50) else: print("❌ 有测试失败，请检查算法实现。") # 输出失败详情 for test, traceback in result.failures + result.errors: print(f"\n失败测试: {test}") print(f"错误信息:\n{traceback}") return result.wasSuccessful()if __name__ == '__main__': # 运行全面测试 success = run_comprehensive_tests() # 退出代码 exit(0 if success else 1)
