# 动态规划

dynamic programming(also know as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions - ideally, using a memory-based data structure.

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

动态规划解决的问题

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，例如求最长递增子序列以及最小编辑距离等等。

动态规划的三要素

重叠子问题：当题目中存在重叠子问题时，利用暴力穷举的话效率会极其低下；
最优子结构：即通过子结构的最值来推导出原问题的最值；何为最优子结构，即每一个子结构之间都是独立的，例如通过已知每个班的最高分，求该年级的最高分；
状态转移方程：最为关键的部分，常常通过暴力解法来得到状态转移方程。

状态转移方程的思考思路

明确 base case（边界条件）
- 明确状态（通常是动态规划问题中会变换的那个变量）
  - 明确选择（即通过不同的选择来得到最优解）
    - 明确 dp 函数/数组的定义（即推到状态方程）

# Leetcode 70 Climbing Stairs

https://leetcode.cn/problems/climbing-stairs/

一次可以爬 1 个台阶，也可以爬 2 个台阶，也就是到 f(n) 有两种途径，那就是 f(n-1) 和 f(n-2)，其实就是斐波那契数列。

思路一：递归

func climbStairs(n int) int {
  if n == 0 {
    return 0
  }
  if n == 1 {
    return 1
  }
  if n == 2 {
    return 2
  }
  return climbStairs(n-1) + climbStairs(n-2)
}

很明显复杂度太高了，其中有过多的重复计算。

思路二：记忆化搜索

加一个 memo []int 来存储 meno[n] 的值，这样对同一个 n，就不需要重复计算了，可以大大降低复杂度。

var memo []int

func climbStairs(n int) int {
    memo = make([]int, n + 1)
    return help(n)
}

func help(n int) int {

    if n == 0 {
        memo[n] = 0 
        return 0
    }
    if n == 1 {
        memo[n] = 1
        return 1
    }
    if n == 2 {
        memo[2] = 2
        return 2
    }
    
    // 如果已经计算过了，那就不需要再重复计算了
    if memo[n] == 0 {
        memo[n] = help(n-1) + help(n-2)
    }

    return memo[n]
}

思路三：动态规划

记忆化搜索其实是自上而下的思路，从 f(n) 出发，到 f(n-1) 和 f(n-2)，一直到最后的 f(1) 和 f(0)，再反推回去得到答案。

动态规划的思想跟这是相反的，动态规划是自下而上，也就是先从 f(0) 和 f(1) 开始，再到 f(2) 和 f(3)，一直到 f(n)。

代码如下：

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    memo := make([]int, n+1)
    memo[0] = 0
    memo[1] = 1
    memo[2] = 2
    for i:=3;i<=n; i++ {
        memo[i] = memo[i-1] + memo[i-2]
    }
    return memo[n]
}

# Leetcode 120 Trangle

https://leetcode.cn/problems/triangle/

明确边界条件

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
明确状态

memo[j][i] 表示从 memo[j][i] 到 底 能找到的最小路径和。
明确选择（即通过不同的选择来得到最优解）

从上层往下层选的两个相邻点的时候，要选那个小的。
明确 dp 函数/数组的定义（即推到状态方程）

f(j,i) = [j,i] + min(f(j+1,i), f(j+1, i+1))，

即 memo[j][i] = triangle[j][i] + min(memo[j+1][i], memo[j+1][i+1])。

// i: 横坐标
// j: 纵坐标
// f(j,i) = [j,i] + min(f(j+1,i), f(j+1, i+1))
func minimumTotal(triangle [][]int) int {
	level := len(triangle)

	if level == 1 {
		return triangle[0][0]
	}
	
  // memo[j][i] 表示从 memo[j][i] 到"底"能找到的最小路径和
	memo := make([][]int, len(triangle))
	for j := 0; j < len(memo); j++ {
		memo[j] = make([]int, len(triangle[j]))
	}

	// 最下面那一行是可以确定的
	for i := 0; i < len(memo[len(memo)-1]); i++ {
		memo[len(memo)-1][i] = triangle[len(memo)-1][i]
	}

	//  从下往上走
	for j := len(triangle) - 2; j >= 0; j-- {
		for i := len(triangle[j]) - 1; i >= 0; i-- {
			// 状态转移
			memo[j][i] = triangle[j][i] + int(math.Min(float64(memo[j+1][i]), float64(memo[j+1][i+1])))
		}
	}

	return memo[0][0]
}

# Leetcode 64 Minimum Path Sum

https://leetcode.cn/problems/minimum-path-sum/

← 回溯法