一、动态规划总结

1.1 题目

一维

斐波那契数列
70.爬楼梯
413.等差数列划分
吃烧饼
343.整数拆分

二维

64.最小路径和
62.不同路径

子序列问题

53.最大连续子序和
300.最长上升子序列
650.只有两个键的键盘

两个字符串

1143.最长公共子序列
72.编辑距离（hard）
10.正则表达式匹配（hard）

1.2 解题思路

题目特征：求某个问题的最优解，并且该问题可以分为多个子问题，子问题之间还有重叠的更小子问题。

思路：

用自上而下的递归思想去分析问题，找到状态转移方程。
用自下而上的循环递推实现，使用dp数组保存子问题的最优解。

二、动态规划题目

斐波那契数列

题目描述：公式为：f(n) = f(n-1) + f(n-2) ，如：112358...

方法1：递归

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

递归树

方法2：动态规划

思路：因为递归有很多重复的计算，所以用数组将子步骤计算的结果都保存下来。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]

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

方法3：状态压缩

思路：因为计算f(n)，只用到了前两个数，所以可以用两个变量来替代dp数组。

int fib3(int n){
    int f_2 = 1;
    int f_1 = 1;
    int res;
    for (int i=3; i<=n; i++) {
        res = f_1 + f_2;
        f_2 = f_1;
        f_1 = res;
    }
    return res;
}

70.爬楼梯

问题描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

解答：基本上是斐波那契数列换了一种问法，数组前几位稍有区别 -> 12358

int climbStairs(int n) {
    int f_2 = 1;
    int f_1 = 1;
    int res = 0;
    for (int i=2; i<=n; i++) {
        res = f_2 + f_1;
        f_2 = f_1;
        f_1 = res;
    }
    return res;
}

413. 等差数列划分

思路：dp[i]表示以nums[i]结尾的等差数列的个数。
结果等于dp数组的总和

int numberOfArithmeticSlices(vector<int>& A) {
    vector<int> dp(A.size(), 0);
    for (int i=2; i<A.size(); i++) {
        if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
            dp[i] = dp[i-1] + 1;
        }
    }
    int sum = accumulate(dp.begin(), dp.end(), 0);
    return sum;
}

吃烧饼

一个烧饼行举办吃烧饼大赛，共n个盘子，第i个盘子有Si个烧饼；
参赛者每次选择1到n中的某个整数x，将1到x盘子中的烧饼吃掉一个，如果Si为0，则无法吃i之后的盘子，问第一个参赛者最多吃多少个烧饼？

思路1：贪心算法

int maxAns(int n, vector<int> nums){
    int ans = 0;
    int endInx = n-1;
    while (endInx >= 0) {
        for (int i=0; i<=endInx; i++) {
            if (nums[i] == 0) {
                endInx = i-1;
                continue;
            }
            ans++;
            nums[i]--;
        }
    }
    return ans;
}

思路2：动态规划
状态转移方程：dp[i] = min(dp[i-1], nums[i]);
结果等于dp数组的和。

int maxAns2(int n, vector<int> nums){
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    for (int i=1; i<nums.size(); i++) {
        dp[i] = min(dp[i-1], nums[i]);
    }
    return accumulate(dp.begin(), dp.end(), 0);
}

343.整数拆分

思路：
状态定义：dp[i]保存着整数i拆分后的最大乘积，
状态转移方程：dp[n] = max(dp[i] * dp[n-i]) i=1..n/2

注意：前三个数字dp[1]、dp[2]、dp[3]较为特殊

dp[1]是因为从2开始才能切分，
dp[2]和dp[3]的数字本身比它拆分后的还要大

int integerBreak(int n) {
    if (n<2) return 0;
    if (n==2) return 1;
    if (n==3) return 2;

    vector<int> dp(n+1,0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for (int i=4; i<=n; i++) {
        int tempMax = 0;
        for (int j=1; j<=i/2; j++) {
            tempMax = max(tempMax, dp[j] * dp[i-j]);
        }
        dp[i] = tempMax;
    }
    return dp[n];
}

64.最小路径和

状态定义：dp[i][j] 是到达 i, j 的最小路径和
状态转移方程：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
注意：第一行和第一列需要特殊处理一下。

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (i-1 == 0) {
                dp[i][j] = dp[i][j-1];
            }else if(j-1 == 0){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
            }
            dp[i][j] += grid[i-1][j-1];
        }
    }
    return dp[m][n];
}

62.不同路径

思路1：DFS。超时。

int dfs(int row, int col, int m, int n){
    if (row>m || col>n) return 0;
    if (row == m && col == n) return 1;
    return dfs(row+1, col, m, n) + dfs(row, col+1, m, n);
}
int uniquePaths2(int m, int n){
    return dfs(1, 1, m, n);
}

思路2：
状态定义：dp[i][j] 是到达 i, j 的最多路径
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意：对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1。

int uniquePaths(int m, int n){
    vector<vector<int>> dp(m+1, vector<int>(n+1, 1));
    for (int i=2; i<=m; i++) {
        for (int j=2; j<=n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m][n];
}

53.最大连续子序和

思路：
状态定义：dp[i]表示已数字nums[i]结尾的连续子数组的最大子序和。
状态转移方程：

如果当前节点加上dp[i-1]，比它自身还小，则dp[i] = nums[i]；
否则：dp[i] = nums[i] + dp[i-1]。

遍历过程中，使用一个变量记录状态数组的最大值。

int maxSubArray(vector<int>& nums) {
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    int max = dp[0];
    for (int i=1; i<nums.size(); i++) {
        int temp = dp[i-1] + nums[i];
        if (temp < nums[i]) {
            dp[i] = nums[i];
        }else{
            dp[i] = temp;
        }
        max = max < dp[i] ? dp[i] : max;
    }
    return max;
}

状态压缩：dp[i]只与dp[i-1]有关，所以dp数组可以压缩为一个变量

int maxSubArray(vector<int>& nums) {
    int dp_i_1 = nums[0];
    int ans = dp_i_1;
    for (int i=1; i<nums.size(); i++) {
        int temp = dp_i_1 + nums[i];
        if (temp < nums[i]) {
            dp_i_1 = nums[i];
        }else{
            dp_i_1 += nums[i];
        }
        ans = max(dp_i_1, ans);
    }
    return ans;
}

300.最长上升子序列

思路：
状态定义：dp[i]保存以当前元素为尾节点的最长上升子序列的长度。
状态转移方程：从后往前比较，找到比它小且dp[j]最大的元素，然后 dp[i]=dp[j]+1

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    vector<int> dp(nums.size(),0);
    dp[0] = 1;
    int res = 1;
    for (int i=1; i<nums.size(); i++) {
        int prevIdx = -1;
        int prevDp = 0;
        for (int j=i-1; j>=0; j--) {
            if (nums[j] < nums[i] && dp[j] > prevDp){
                prevDp = dp[j];
                prevIdx = j;
            }
        }
        
        if (prevIdx < 0) dp[i] = 1;
        else dp[i] = dp[prevIdx] + 1;
        
        res = max(res, dp[i]);
    }
    return res;
}

650.只有两个键的键盘

思路：dp[i]表示需要操作多少步才能得到

状态转移方程：

如果这个数有因子，则dp[i] = dp[j] + dp[i/j];
如果是素数，则dp[i] = i;

int minSteps(int n) {
    vector<int> dp(n+1, 0);
    for (int i=2; i<=n; i++) {
        dp[i] = i;
        for (int j=2; j<=n/2; j++) {
            if (i%j == 0) {
                dp[i] = dp[j] + dp[i/j];
                break;
            }
        }
    }
    return dp[n];
}

1143.最长公共子序列

题目描述：公共子序列可以不连续。
思路：

状态定义：dp[i][j]保存着当前元素为尾节点的最长公共子序列长度
状态转移方程：

如果当前text1[i]，text2[j]相等，dp[i][j] = dp[i-1][j-1] + 1
如果当前text1[i]，text2[j]不相等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

以"acbcbcef"和"abcbced"为例，动态规划数组如下图所示：

该图是公共子序列连续的情况：

如果当前text1[i]，text2[j]不相等，dp[i][j] = 0；

在该题中公共子序列可以不连续的情况：

如果当前text1[i]，text2[j]不相等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

int longestCommonSubsequence(string text1, string text2) {
    int rows = text1.size();
    int cols = text2.size();
    
    // 多使用一行和一列
    vector<int> d(cols+1, 0);
    vector<vector<int>> dp(rows+1, d);
    
    for (int i=1; i<=rows; i++) {
        for (int j=1; j<=cols; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[rows][cols];
}

72. 编辑距离

题目描述：将 word1 转换成 word2 所使用的最少操作数。

例子1：penumu 和 u
例子2：zoo 和 zo

思路：除了基本的动态规划思路之外，多使用一行和一列来辅助计算，这很重要！
可以对数组进行统一计算，且对特殊情况（如某一方为""）也适用。