如何将此递归转换为 dp

Question

我正在尝试解决 this 问题。我相信我的解决方案确实有效，但需要更多时间。这是我的解决方案 - 在每一步，如果我选择 i 或 i+1 索引，我都会计算最小总和。

class Solution 
{
    public int minimumTotal(List<List<Integer>> triangle) 
    {
        return minSum( triangle, 0, 0 );
    }
        
    public int minSum( List<List<Integer>> triangle, int row, int index )
    {
           if( row >= triangle.size() )
               return 0;

            int valueAtThisRow = triangle.get(row).get(index);

            return Math.min( valueAtThisRow + minSum(triangle, row+1, index), 
                             valueAtThisRow + minSum(triangle, row+1, index+1));
    }
}

我觉得用DP比较合适。请分享有关如何将其转换为 DP 的任何建议。

Answer 1

我认为自下而上的解决方案在这里更简单，不需要额外的内存，我们可以将中间结果存储在相同的 list/array 个单元格中

从上一层开始遍历三角形的各层，为每个元素从两个可能的结果中选择最好的结果，然后移动到上一层，依此类推。之后 triangle[0][0] 将包含最小总和

for (row = n - 2; row >= 0; row--)
    for (i = 0; i <= row; i++)
          triangle[row][i] += min(triangle[row+1][i], triangle[row+1][i+1])

（试过python版本，接受）

Answer 2

DP 自底向上方法：

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        vector<int> mini = triangle[triangle.size()-1];
        for ( int i = triangle.size() - 2; i>= 0 ; --i )
            for ( int j = 0; j < triangle[i].size() ; ++ j )
                mini[j] = triangle[i][j] + min(mini[j],mini[j+1]);
        return mini[0];
    }
};

Python版本：

def minimumTotal(self, triangle: List[List[int]]) -> int:
        
        if not triangle: return 
        size = len(triangle)
        res  = triangle[-1]    # last row
        
        for r in range(size-2, -1, -1):      # bottom up
            for c in range(len(triangle[r])):
                res[c] = min(res[c], res[c+1]) + triangle[r][c]
        
        return res[0]

Answer 3

自上而下的解决方案：我们从三角形的顶部开始逐行计算到每个单元格的最短路径 (agenda)。

C#代码

public int MinimumTotal(IList<IList<int>> triangle) {
    int[] agenda = new int[] {triangle[0][0]};
    
    for (int r = 1; r < triangle.Count; ++r) {
        int[] next = triangle[r].ToArray();
        
        for (int c = 0; c < next.Length; ++c) 
            if (c == 0)
                next[c] += agenda[c];
            else if (c == next.Length - 1)
                next[c] += agenda[c - 1];
            else
                next[c] += Math.Min(agenda[c - 1], agenda[c]);
                    
        agenda = next;
    }
    
    return agenda.Min(); 
}

如何将此递归转换为 dp

How do I convert this recursion to dp

algorithm

dynamic-programming