120。三角形最小路径和题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/triangle题目给定一个三角形，求出从上到下的最小路径和。每一步只能移动到下一行的相邻节点。这里的相邻节点是指下标与前一个节点下标相同或等于前一个节点下标+1的两个节点。例如给定三角形：[[2],[3,4],[6,5,7],[4,1,8,3]]自上而下的最小路径和为11（即2+3+5+1=11）。解题思路：递归，动态规划先看题目中的提示，【这里的相邻节点指的是与前一个节点下标相同或者等于前一个节点下标的下标+1两个节点的]。我们让f(i,j)是从点(i,j)到底部的路径的最小总和。现在根据上面的提示，很容易得到公式：f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle[i][j]也就是说需要的路径和是：取与当前节点相邻的两个节点的最小值，加上当前节点的值。递归首先尝试用递归的方法来解决。根据上面的公式，直接粘贴代码：,i,j):#设置终止条件ifi==len(triangle):return0#直接用公式returnmin(self.path(triangle,i+1,j),self.path(triangle,i+1,j+1))+triangle[i][j]上面代码因为大量重复计算导致执行超时，现在考虑优化。递归（优化）这里采用创建备忘录的方式，避免重复计算，代码也贴在这里：classSolution:defminimumTotal(self,triangle:List[List[int]])->int:#memomemo={}defpath(triangle,i,j):#设置终止条件ifi==len(triangle):return0if(i,j)inmemo:returnmemo[(i,j)]memo[(i,j)]=min(path(triangle,i+1,j),path(triangle,i+1,j+1))+triangle[i][j]#直接用公式returnmin(path(triangle,i+1,j),path(triangle,i+1,j+1))+triangle[i][j]returnpath(triangle,0,0)以上方法都是自上而下的，现在我们尝试使用动态规划来实现自下而上的解决方案。动态规划采用动态规划的解法，首先定义状态。状态定义令dp[i][j]为从点(i,j)到底部的路径的最小总和。状态转移方程同理，我们可以根据一开始得到的公式得到状态转移方程：dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]具体代码实现见【代码实现#动态规划】在上面动态规划（空间优化）的动态规划算法中，我们定义了一个二维数组。当我们计算dp[i][j]时，我们在下一行使用dp[i+1][j]和dp[i+1][j+1]。那么我们可以直接考虑自底向上定义一个一维数组。具体代码实现见【代码实现#动态规划（空间优化）】代码实现#动态规划类解决方案：defminimumTotal(self,triangle:List[List[int]])->int:m=len(triangle)dp=[[0]*(m+1)for_inrange(m+1)]foriinrange(m-1,-1,-1):forjinrange(0,i+1):dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]returndp[0][0]#动态编程（空间优化）类解决方案：defminimumTotal(self,triangle:List[List[int]])->int:m=len(triangle)dp=[0]*(m+1)foriinrange(m-1,-1,-1):对于范围(0,i+1)中的j:dp[j]=min(dp[j],dp[j+1])+triangle[i][j]返回dp[0]实现动态规划的结果（优化前）欢迎关注公众号【书籍收藏】
