一、记忆化搜索--自上而下解决问题

1、例如斐波那切数列问题

常规的我们是利用递归进行处理，但是当数值比较大时，导致重复的计算，因此时间复杂度也会增大，所以可以采用数组将值进行存储，在递归之前进行判断。

二、动态规划

动态规划的题目，首先理清题目的递归情况，然后使用记忆化方法解决问题，最后可以自底向上的使用动态规划来解决

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

（一）记忆化方法解决问题

class Solution {
private:
    vector temp;
    int MAX(int a,int b,int c){
        return max(a,max(b,c));
    }
    int breakInteger(int n ){
        if(n == 1)
            return 1;
        if(temp[n] != -1)
            return temp[n];
        int res = -1;
        for(int i = 1 ; i < n ; i++){
            res = MAX(res,i*(n-i),i*breakInteger(n-i));
        }
        temp[n] = res;
        return res;
    }
public:
    int integerBreak(int n) {
        temp = vector(n+1,-1);
        return breakInteger(n);
    }
};

（二）动态规划方法解决问题

class Solution {
private:
    vector temp;
    int MAX(int a,int b,int c){
        return max(a,max(b,c));
    }

public:
    int integerBreak(int n) {
        temp = vector(n+1,-1);
        temp[1] = 1;
        for(int i = 2 ; i <=n ; i++){
            for(int j = 1 ; j <= i-1 ; j ++){
                temp[i] = MAX(temp[i],j * (i-j),j * temp[i-j]);
            }
        }
        return temp[n];
    }
};

0-1背包问题

记忆化搜索：

动态规划方法：

优化后的代码：

更多动态规划问题

1、最长公共子序列问题

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。

2、正则表达式匹配

func isMatch(s string, p string) bool {
    m := len(s)
    n := len(p)
    s = " " + s
    p = " " + p
    var dp = make([][]bool,m+1)
    for i := 0 ; i < m+1 ; i ++ {
        dp[i] = make([]bool,n+1)
    }
    //所有s[1...i] 和 p[1...j]的匹配结果
    dp[0][0] = true

    for i := 0 ; i <= m ; i ++ {
        for j := 1 ; j <= n ; j++ {
            if j + 1 <= n && p[j+1] == '*'{
                continue
            }
            if i > 0 && p[j] != '*'{
                dp[i][j] = dp[i-1][j-1] &&(s[i]==p[j]||p[j]=='.')
            }else if p[j] == '*'{
                dp[i][j] = dp[i][j-2] || i > 0 && dp[i-1][j] && (s[i]==p[j-1]||p[j-1]=='.')
            }
        }
    }
    return dp[m][n]
}

3、通配符匹配

//dp[i][j]表示s[1..i]和p[1..j]是否匹配
func isMatch(s string, p string) bool {
    m := len(s)
    n := len(p)
    s = " " + s
    p = " " + p
     dp := make([][]bool,m+1)
     for i := 0 ; i < m+1 ; i++ {
         dp[i] = make([]bool,n+1)
     }
     dp[0][0] = true

     for i := 0 ; i < m+1 ; i++ {
         for j := 1 ; j < n+1 ; j++ {
             if p[j] != '*' {
                 dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i]==p[j] || p[j]=='?')
             }else{
                 dp[i][j] = dp[i][j-1] || i > 0 && dp[i-1][j]
             }
         }
     }
     return dp[m][n]
}

4、不同路径

func uniquePaths(m int, n int) int {
     dp := make([][]int,m)
     for i := 0 ; i < m ; i++{
         dp[i] = make([]int,n)
     }
     for i := 0 ; i < m ; i++ {
         for j := 0 ; j < n ; j++ {
                 if i == 0 && j == 0 {
                     dp[i][j] = 1
                 }else{
                     if i > 0 {
                         dp[i][j] += dp[i-1][j]
                     }
                     if j > 0 {
                         dp[i][j] += dp[i][j-1]
                     }
                 }
         }
     }
     return dp[m-1][n-1]
}