如何修改基于Dynamic Programming的Coin Collecting Problem算法以支持任意起点与不可达单元格？

原问题与修改需求 #

已实现基于动态规划的硬币收集问题代码：原规则为机器人从棋盘左上角出发，仅能向右/向下移动至右下角，需计算最大收集硬币数并打印路径。现需修改为：

• 机器人可从任意可达单元格出发
• 棋盘存在不可达单元格（机器人无法进入）

原实现代码 #

获取最大硬币数的max_coin_picked函数 #

def max_coin_picked(self):
    # 该算法遵循动态规划原理解决硬币收集问题
    for i in range(self.row):  # 5行
        for j in range(self.column):  # 6列
            if i == 0 and j == 0:
                self.gameBoard[i][j] = 0 + self.gameBoard[i][j]
            elif i == 0:
                self.gameBoard[i][j] = max(0, self.gameBoard[i][j - 1]) + self.gameBoard[i][j]
            elif j == 0:
                self.gameBoard[i][j] = max(self.gameBoard[i - 1][j], 0) + self.gameBoard[i][j]
            else:
                self.gameBoard[i][j] = max(self.gameBoard[i - 1][j], self.gameBoard[i][j - 1]) + self.gameBoard[i][j]

    # 获取从初始位置出发能收集的最大硬币数
    maxCoinPicked = self.gameBoard[self.row - 1][self.column - 1]
    return maxCoinPicked

打印路径的path函数 #

def path(self):
    # 反向遍历棋盘以回溯路径
    row = self.row - 1  # 4
    column = self.column - 1  # 5

    # 标记终点
    self.gameBoard[row][column] = '*'

    # 向上回溯直到第一行
    while row >= 1:
        if column != 0 and (self.gameBoard[row][column - 1] > self.gameBoard[row - 1][column]):  # 向左回溯
            # 移动到左侧单元格并标记
            self.gameBoard[row][column - 1] = '*'
            column = column - 1
        else:
            # 移动到上方单元格并标记
            self.gameBoard[row - 1][column] = '*'
            row = row - 1

    # 标记第一行剩余的路径单元格
    column = column - 1
    while column >= 0:
        self.gameBoard[0][column] = '*'
        column = column - 1

    return self.gameBoard

修改后的实现方案 #

核心思路 #

1. 不可达单元格标记：用-inf表示不可达，动态规划过程中跳过此类单元格，禁止从不可达单元格转移。
2. 任意起点支持：DP表初始时，每个可达单元格的值设为自身硬币数（作为起点的情况），后续通过上方/左方的有效转移更新最大硬币数。
3. 路径回溯优化：反向遍历DP表，根据转移关系回溯到起点，避免修改原始棋盘。

修改后的max_coin_picked函数 #

def max_coin_picked(self):
    INF = float('-inf')
    # 初始化DP表，分离原始棋盘与计算表
    self.dp_table = [[INF for _ in range(self.column)] for _ in range(self.row)]
    for i in range(self.row):
        for j in range(self.column):
            # 可达单元格初始值为自身硬币数（作为起点）
            if self.original_board[i][j] is not None:
                self.dp_table[i][j] = self.original_board[i][j]
    
    # 动态规划填充DP表
    for i in range(self.row):
        for j in range(self.column):
            if self.original_board[i][j] is None:
                continue  # 跳过不可达单元格
            
            # 从上方单元格转移
            if i > 0 and self.dp_table[i-1][j] != INF:
                self.dp_table[i][j] = max(self.dp_table[i][j], self.dp_table[i-1][j] + self.original_board[i][j])
            # 从左方单元格转移
            if j > 0 and self.dp_table[i][j-1] != INF:
                self.dp_table[i][j] = max(self.dp_table[i][j], self.dp_table[i][j-1] + self.original_board[i][j])
    
    # 若要求必须到达右下角，返回对应值；若允许到任意单元格，遍历取最大值
    target_row, target_col = self.row-1, self.column-1
    max_coin = self.dp_table[target_row][target_col]
    return max_coin if max_coin != INF else 0

修改后的path函数 #

def path(self):
    INF = float('-inf')
    target_row, target_col = self.row-1, self.column-1
    
    # 检查终点是否可达
    if self.dp_table[target_row][target_col] == INF:
        return "无法到达右下角"
    
    # 初始化路径棋盘，避免修改原始数据
    path_board = [[' ' for _ in range(self.column)] for _ in range(self.row)]
    path_board[target_row][target_col] = '*'
    
    current_row, current_col = target_row, target_col
    # 回溯路径至起点
    while True:
        from_up = False
        from_left = False
        
        # 判断是否从上方转移而来
        if current_row > 0 and self.dp_table[current_row-1][current_col] != INF:
            if self.dp_table[current_row][current_col] == self.dp_table[current_row-1][current_col] + self.original_board[current_row][current_col]:
                from_up = True
        # 判断是否从左方转移而来
        if current_col > 0 and self.dp_table[current_row][current_col-1] != INF:
            if self.dp_table[current_row][current_col] == self.dp_table[current_row][current_col-1] + self.original_board[current_row][current_col]:
                from_left = True
        
        # 移动至前一个单元格并标记
        if from_up:
            current_row -= 1
        elif from_left:
            current_col -= 1
        else:
            break  # 到达起点
        
        path_board[current_row][current_col] = '*'
    
    return path_board

注意事项 #

• 需将原始棋盘存储为self.original_board，不可达单元格用None标记（可根据实际需求替换为其他标记值）。
• 若允许机器人到达任意单元格而非仅右下角，可修改max_coin_picked函数，遍历整个DP表取最大值。

内容的提问来源于stack exchange，提问作者Mohamed Khaled