Dynamic Programming

概述

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

• 设计感比较强
• 艺术性比较强
  

  递归

  原斐波那契数列，算法复杂度$O(2^n)$

int fib(int n) {
    if (n == 0 || n == 1) return n;
    
    return fib(n - 1) + fib(n - 2);
}

优化， 加入一个数组保存每次运算的值

记忆化搜索

自上而下的解

vector<int> memo(n + 1, -1);
int fib(int n) {
    if (n == 0 || n == 1) return n;
    
    if (memo[n] == -1) {
        memo[n] = fib(n - 1) + fib(n - 2);
    }
    return memo[n];
}

动态规划

自下而上的解

int fib(int n) {
    vector<int> memo(n + 1, -1);
    
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= n; i ++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

LeetCode练习题

• No.120 Triangle
• No.64 Minimum Path Sum

例题：No.343 Integer Break

记忆化搜索：自顶向下

int max3(int a, int b, int c) {
    return max(a, max(b, c));
}
int breakInteger(int n, vector<int>& memo) {
    if (n == 1) return 1;
    
    if (memo[n] != -1) {
        return memo[n];
    }
    int res = -1;
    for (int i = 1; i < n; i ++) {
        res = max3(res, i * (n - i), i * breakInteger(n - i, memo));
    }
    memo[n] = res;
    return memo[n];
}


int integerBreak(int n) {
    vector<int> memo(n+1, -1);
    return breakInteger(n, memo);
}

动态规划：自下而上

int integerBreak(int n ) {
    vector<int> memo(n + 1, -1);
    memo[1] = 1;
    
    for (int i = 2; i <= n; i ++) { //对每个可能的i进行遍历
        for (int j = 1; j < i; j ++) {// i下面每个可能的组合：(j, i - j)
            //对三种情况比较，1. 内存中前最大值；2. 当前组合(i, i - j)的乘积值；3.i - j可能的组合最大值乘j
            memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);
        }
    }
    return memo[n];
}

LeetCode练习题

• No.279 Perfect Squares

  class Solution {
  public:
      int numSquares(int n) {        
          if (n <= 0) return 0;
          vector<int> step(n + 1, INT_MAX);
          step[0] = 0;
          step[1] = 1;
          
          for (int i = 2; i <= n; i ++) {
              int j = 1;
              
              while (i >= j) {
                  step[i] = min(step[i], step[i - j * j] + 1);
                  j ++;
              }
              
          }
          return step[n];
          
      }
  };

• No.91 Decode Ways

• No.62 Unique Paths
• No.63 Unique PathsII

例题：No.198 House Robber

状态转移

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> price(n + 1, 0);
        
        price[1] = nums[0];
        price[2] = nums[1];
        
        for (int i = 2; i < n; i++) {
            price[i + 1] = max(price[i - 1], price[i - 2]) + nums[i];
        }
        
        return max(price[n], price[n - 1]);
    }
};

LeetCode练习题

• No.213 House Robber II
• No.337 House Robber III
• No.309 Best Time to Buy and Sell Stock with Cooldown

看不懂，不会做啊啊啊！！！w(ﾟДﾟ)w

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<int> buy(n, 0);
        vector<int> sell(n, 0);
        vector<int> rest(n, 0);
        
        buy[0] = 0 - prices[0];
        sell[0] = 0;
        rest[0] = 0;
        
        for (int i = 1; i < n; i ++) {
            buy[i] = max(rest[i - 1] - prices[i], buy[i - 1]);
            sell[i] = max(buy[i - 1] + prices[i], sell[i - 1]);
            //rest[i] = max(buy[i - 1], max(sell[i - 1], rest[i - 1]));  
            rest[i] = sell[i - 1];
        }
        return sell[n - 1];
    }
};

背包问题：

例题

练习题：

• 完全背包问题
• 多维费用背包问题

最长上升子序列

例题：No.300 Longest Increasint Subsequence

int lengthOfLIS(vector<int> nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> len(n, 1);
    int res = 0;
    for (int i = 0; i < n; ++) {
        for (int j = i - 1; j >= 0; j --) {
            if (nums[i] > nums[j]) {
               len[i] = max(len[i], len[j] + 1); 
            }
            
        }
        res = max(res, len[i]);
    }
    
    return res;
}

LeetCode练习题

• No.376 Wiggle Subsequence

$O(n^2)$的解法，更好懂一些

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> larger(n, 1);
        vector<int> less(n, 1);
        for (int i = 1; i < n; i ++) {
            for (int j = 0; j < i; j ++) {
                if (nums[i] > nums[j]) 
                    larger[i] = max(larger[i], less[j] + 1);
                if (nums[i] < nums[j]) {
                    less[i] = max(less[i], larger[j] + 1);
                }
            }
        }
        return max(larger[n - 1], less[n - 1]);
    }
};

$o(n)$的解法，我至今是懵逼的

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> larger(n, 1);
        vector<int> less(n, 1);
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                larger[i] = less[i - 1] + 1;
                less[i] = less[i - 1];
            }
            if (nums[i] < nums[i - 1]) {
                less[i] = larger[i - 1] + 1;
                larger[i] = larger[i - 1];
            }
            if (nums[i] == nums[i - 1]) {
                larger[i] = larger[i - 1];
                less[i] = less[i - 1];
            }
        }
        return max(larger[n - 1], less[n - 1]);
    }
};

最长公共子序列

int LCS(string a, string b) {
    int n = a.size();
    int m = b.size();
    if (n == 0 || m == 0) return 0;
    vector<vector<int>> memo(n, vector<int>(m + 1, 0));
    
    for (int j = 1; j <= m; j ++) {
        memo[0][j] = max(memo[0][j - 1], a[0] == b[j - 1] ? 1 : 0);
    }
    
    for (int i = 1; i < n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (b[j - 1]  == a[i]) {
                memo[i][j] = memo[i - 1][j - 1] + 1;
            }
            else {
                memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]);
            }
        }
    }
    return memo[n - 1][m];
}

dijkstra单源最短路径算法

有权图最短路径

$$shortestPath(i) = min(shortestPath(j) + w(i, j))$$