Basics on Dynamic Programming(DP) 1 - Intro

Learn the basics on DP througe some examples

1. Why use DP - Triangle - Leetcode 120

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

1) 原始的解法, DFS解法, 爆炸性复杂度2^n, 伪代码:

// traversal 
int minimumTotal(vector<vector<int> > &triangle) {
  int n = triangle.size();  // n is the height
  int best = INT_MAX;
  dfs(triangle, 0, 0, 0, best);  // sum is root->x,y, not include root
  return best;
}
void dfs(vector<vector<int> > &triangle, int x, int y, int sum, int &best) {
  if(x == triangle.size()) {
    best = min(best, sum);
    return;
  }
  dfs(triangle, x + 1, y, sum + triangle[x][y], best);
  dfs(triangle, x + 1, y+1, sum + triangle[x][y], best); //sum这时包括了root点
}

2) 此类方法的优化:

  • 如果没解了,就不搜了(可行性剪枝) 不可行
  • 如果解不可能最优,就不搜了(最优性剪枝) 可尝试
  • 看看有没有重复计算, 伪代码如下:
// 代表了从xy出发,走到最底层的最短路是多少. 变化:有返回值了
int dfs(int x, int y) {    
    if (x == n) {
        return 0;
    }
    
    if (flag[x][y]) {  //重复计算。标记算过了
        return hash[x][y];
    }
    flag[x][y] = true;
    hash[x][y] = min(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y];
    return hash[x][y];
}
 
dfs(0, 0)
0,0 -> (1,0), (1,1)
(1,0) -> (2,0), (2,1)
(1,1) -> (2,1), (2,2)

复杂度O(n^2),n为所有的点的个数,求出了每个点到所有点的距离

3) 动态规划,思路:

1
2 3
4 5 6
7 8 9 10

state: f[i][j]代表就是从i,j出发,到最底层的最短路
function: f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + a[i][j]
intialize: f[n][x] = 0; //越界的那一层
answer: f[0][0]

记忆化搜索–动态规划最本质的思想:

  • Advantage: Easy to think and implement
  • Disadvantage: Expensive memory cost.

二维数组代码:

int minimumTotal(vector<vector<int> > &triangle) {
    int size = triangle.size();
    if(size == 0)   return 0;
    //从下往上
    vector<vector<int> > dp(triangle);
    for(int i=size-2; i>=0; i--) {
        for(int j=0; j<=i; j++)
            dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
    }
    return dp[0][0];
}

压缩空间:

  • 当第i层状态,只跟i-1有关,就可压缩成一维的。把i-2以前的都扔掉
  • DP大类1:Two Sequence Dp 一般都可以压缩空间
  • DP大类2:sequence一般不可以,貌似本来就是一维的(后边具体分析).
int minimumTotal(vector<vector<int> > &triangle) {
    int size = triangle.size();
    if(size == 0)   return 0;
    //从下往上
    vector<int> dp(triangle[size-1]);   //用最后一行初始化!
    for(int i=size-2; i>=0; i--) {
        for(int j=0; j<=i; j++)
            dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];  //从前往后,不会覆盖需要的
    }
    return dp[0];
}

2. Clues: 如何想到使用DP

  • Can not sort.
  • Find a maximum/minimum result
  • Decide whether something is possible or not
  • Count all possbile solutions: doesn’t care about the solution details, only the count or possibility(若求所有的排列,只能全搜)

什么情况下不使用DP:

  • 求出所有具体的方案,不只是个数,只能全搜
  • 输入数据是一个集合(无序的),而不是序列
  • 暴力算法的复杂度已经是多项式级别(不适合n^3–>n^2),适合2^n/n! –> n^2/n^3

3. 动态规划的4点要素

  • 状态 State (灵感,创造力,存储小规模问题的结果)
  • 方程 Function (状态之间的联系,怎么通过小的状态,来算大的状态)
  • 初始化 Intialization (最极限的小状态是什么)
  • 答案 Answer (最大的那个状态是什么)
Loading Disqus comments...
Table of Contents