关于leetcode个人解题总结:一道经典的动态规划入门题leetcode64

36次阅读

共计 1065 个字符，预计需要花费 3 分钟才能阅读完成。

动静布局的几个前提条件：
最优子结构性质
无后向性
子问题的重叠性

显然这道题是满足动静布局的解题条件的
每个门路的长度取决于之前门路的值
求解最大门路的过程中须要屡次用到之前求出的子门路的长度
易得状态转移方程为

当 i>0 且 j>0 时，

当 i 或 j 有一个等于 0 时，则无需思考子门路的抉择，即为

代码

func minPathSum(grid [][]int) int {
    // 构建一个二维数组
    m,n:=len(grid),len(grid[0])
    order:=make([][]int,m)
    for i:=range order{order[i]=make([]int,n)
    }
    // 计算门路长度
    order[0][0]=grid[0][0]
    for i:=1;i<n;i++{order[0][i]=order[0][i-1]+grid[0][i]
    }
    for i:=1;i<m;i++{order[i][0]=order[i-1][0]+grid[i][0]
    }
    for i:=1;i<m;i++{
        for j:=1;j<n;j++{order[i][j]=grid[i][j]+min(order[i-1][j],order[i][j-1])
        }
    }
    return order[m-1][n-1]

}
func min(a int,b int)int{if a<b {return a}
    return b
}

成果

此时
工夫复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。须要对整个网格遍历一次，计算 dp 的每个元素的值。

空间复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。创立一个二维数组 dp，和网格大小雷同。

空间复杂度能够优化，例如每次只存储上一行的 \textit{dp}dp 值，则能够将空间复杂度优化到 O(n)O(n)

代码

func minPathSum(grid [][]int) int {
    // 构建一个二维数组
    m,n:=len(grid),len(grid[0])
    last:=make([]int,n)
    now:=make([]int,n)

    last[0]=grid[0][0]
    for i:=1;i<n;i++{last[i]=last[i-1]+grid[0][i]
    }
    now=last
    for i:=1;i<m;i++{now[0]=last[0]+grid[i][0]
        for j:=1;j<n;j++{now[j]=grid[i][j]+min(last[j],now[j-1])
        }
        last=now
    }
    return now[n-1]

}
func min(a int,b int)int{if a<b {return a}
    return b
}

成果

正文完