func minPathSum(grid [][]int) int {
// 思路：动态规划
// f[i][j] 表示i,j到0,0的和最小
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
// 复用原来的矩阵列表
// 初始化：f[i][0]、f[0][j]
for i := 1; i < len(grid); i++ {
grid[i][0] = grid[i][0] + grid[i-1][0]
}
for j := 1; j < len(grid[0]); j++ {
grid[0][j] = grid[0][j] + grid[0][j-1]
}
for i := 1; i < len(grid); i++ {
for j := 1; j < len(grid[i]); j++ {
grid[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
}
}
return grid[len(grid)-1][len(grid[0])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？
func uniquePaths(m int, n int) int {
// f[i][j] 表示i,j到0,0路径数
f := make([][]int, m)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if f[i] == nil {
f[i] = make([]int, n)
}
f[i][j] = 1
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
return f[m-1][n-1]
}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
// f[i][j] = f[i-1][j] + f[i][j-1] 并检查障碍物
if obstacleGrid[0][0] == 1 {
return 0
}
m := len(obstacleGrid)
n := len(obstacleGrid[0])
f := make([][]int, m)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if f[i] == nil {
f[i] = make([]int, n)
}
f[i][j] = 1
}
}
for i := 1; i < m; i++ {
if obstacleGrid[i][0] == 1 || f[i-1][0] == 0 {
f[i][0] = 0
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] == 1 || f[0][j-1] == 0 {
f[0][j] = 0
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 1 {
f[i][j] = 0
} else {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
}
return f[m-1][n-1]
}
2、序列类型（40%）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
func climbStairs(n int) int {
// f[i] = f[i-1] + f[i-2]
if n == 1 || n == 0 {
return n
}
f := make([]int, n+1)
f[1] = 1
f[2] = 2
for i := 3; i <= n; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}
func coinChange(coins []int, amount int) int {
// 状态 dp[i]表示金额为i时，组成的最小硬币个数
// 推导 dp[i] = min(dp[i-1], dp[i-2], dp[i-5])+1, 前提 i-coins[j] > 0
// 初始化为最大值 dp[i]=amount+1
// 返回值 dp[n] or dp[n]>amount =>-1
dp:=make([]int,amount+1)
for i:=0;i<=amount;i++{
dp[i]=amount+1
}
dp[0]=0
for i:=1;i<=amount;i++{
for j:=0;j<len(coins);j++{
if i-coins[j]>=0 {
dp[i]=min(dp[i],dp[i-coins[j]]+1)
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
func min(a,b int)int{
if a>b{
return b
}
return a
}
注意
dp[i-a[j]] 决策 a[j]是否参与
在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为 m，每个物品的大小为 A[i]
func backPack (m int, A []int) int {
// write your code here
// f[i][j] 前i个物品，是否能装j
// f[i][j] =f[i-1][j] f[i-1][j-a[i] j>a[i]
// f[0][0]=true f[...][0]=true
// f[n][X]
f:=make([][]bool,len(A)+1)
for i:=0;i<=len(A);i++{
f[i]=make([]bool,m+1)
}
f[0][0]=true
for i:=1;i<=len(A);i++{
for j:=0;j<=m;j++{
f[i][j]=f[i-1][j]
if j-A[i-1]>=0 && f[i-1][j-A[i-1]]{
f[i][j]=true
}
}
}
for i:=m;i>=0;i--{
if f[len(A)][i] {
return i
}
}
return 0
}
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值. 问最多能装入背包的总价值是多大?
思路：f[i][j] 前 i 个物品，装入 j 背包 最大价值
func backPackII (m int, A []int, V []int) int {
// write your code here
// f[i][j] 前i个物品，装入j背包 最大价值
// f[i][j] =max(f[i-1][j] ,f[i-1][j-A[i]]+V[i]) 是否加入A[i]物品
// f[0][0]=0 f[0][...]=0 f[...][0]=0
f:=make([][]int,len(A)+1)
for i:=0;i<len(A)+1;i++{
f[i]=make([]int,m+1)
}
for i:=1;i<=len(A);i++{
for j:=0;j<=m;j++{
f[i][j]=f[i-1][j]
if j-A[i-1] >= 0{
f[i][j]=max(f[i-1][j],f[i-1][j-A[i-1]]+V[i-1])
}
}
}
return f[len(A)][m]
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
