动态规划总结 | Solo

唔，学了两个星期的动规，感觉入了一点点门了吧，当时学的时候没有系统的整理，现在回过头来整理可能又要花两三天（毕竟50多到题呢），趁着lintcode vip还没到期抓紧整理一下。长途路漫长，要学的还有很多呀。加油吧骚年。
有些动规可以用记忆化搜索来做，或者可以用滚动数组

[toc]

例题

669. Coin Change

题目链接

题目大意：
给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

分析：

状态变量：f[i] 表示组成i的最小方案的个数
最后一步： f[s] = f[s - a[j]] + 1
转移方程： f[i] = min(f[i], f[i - a[j]])
初始化和边界情况： f[0] = 0, i >= a[j]
计算顺序：从前往后，一般的动规都是这样算的

AC代码：

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int> &a, int s) {
        int n = a.size();
        if (n == 0)
            return -1;
        int f[s + 1];
        f[0] = 0;
        for (int i = 1; i <= s; i++){
            f[i] = INF;
            for (int j = 0; j < n; j++){
                if (i >= a[j])
                    f[i] = min(f[i], f[i - a[j]] + 1);
            }
        }
        if (f[s] != INF)
            return f[s];
        return -1;
    }
};

114. Unique Paths

题目链接

题目大意

有一个机器人的位于一个 m × n 个网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

n和m均不超过100

AC代码

class Solution {
public:
    
    int uniquePaths(int m, int n) {
        int f[m][n];

        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (i == 0 || j == 0){ //把初始化放在里面也挺常用的哦
                    f[i][j] = 1;
                    continue;
                }
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
};

116. Jump Game

题目链接

题目大意
给出一个非负整数数组，你最初定位在数组的第一个位置。　　　

数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　　

判断你是否能到达数组的最后一个位置。

AC代码（DP）

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &a) {
        int n = a.size();
        if (n == 1)
            return true;
        bool f[n];
        f[0] = 1;
        for (int i = 1; i < n; i++){
            f[i] = false;
            for (int j = i - 1; j >= 0; j--){
                if ((j + a[j] >= i) && f[j]){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];
    }
};

AC代码（贪心）

class Solution {
public:

    bool canJump(vector<int> &a) {
        int n = a.size();
        if (n == 1)
            return true;
        int maxn = 0;
        for (int i = 0; i < n; i++){
            if (i > maxn)
                return false;
            else if (maxn >= n - 1)
                return true;
            else
                maxn = max(maxn, i + a[i]);
        }
        return true;
    }
};

115. Unique Paths II

题目链接

题目描述
现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。

m 和 n 均不超过100

分析
一样想就行啦

AC代码

class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    int uniquePathsWithObstacles(vector<vector<int>> &a) {
        // write your code here
        int m = a.size();
        int n = a[0].size();
        int f[101][101];
        
        f[0][0] = !a[0][0];
        for (int i = 1; i < m; i++){
            if (!a[i][0])
                f[i][0] = f[i - 1][0];
            else
                f[i][0] = 0;
        }
        for (int i = 1; i < n; i++){
            if (!a[0][i])
                f[0][i] = f[0][i - 1];
            else
                f[0][i] = 0;
        }
        
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                if (!a[i][j])
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                else
                    f[i][j] = 0;
            }
        }
        return f[m - 1][n - 1];
    }
    
};

515. Paint House

题目链接

题目描述
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。

费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。

分析

状态变量 f[i][j] 代表前i个屋子（即0 ~ i - 1）当第i - 1个屋子染成j颜色时的最小话费
转移方程 f[i][j] = min(f[i][j], f[i - 1][k] + a[i - 1][j]) | k != j
初始化和边界条件前0栋房子花费为0 f[0][j] = 0
计算顺序从前向后

AC代码

class Solution {
public:

    int minCost(vector<vector<int>> &a) {
        // write your code here
        int n = a.size();
        const int INF = 0x3f3f3f3f;
        int f[n + 1][3];
        memset(f[0], 0, sizeof f[0]);
        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= 2; j++){
                f[i][j] = INF;
                for (int k = 0; k <= 2; k++){
                    if (k == j)
                        continue;
                    f[i][j] = min(f[i][j], f[i - 1][k] + a[i - 1][j]);
                }
            }
        }
        return min(min(f[n][0], f[n][1]), f[n][2]);
    }
};

512. Decode Ways

题目链接

题目描述
有一个消息包含A-Z通过以下规则编码

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

分析
只分析一下最后一步吧，最后一步要不就是f[n] += f[n - 1] 要不就是 f[n] += f[n - 2] | 最后两位是大于9小于27

AC代码

class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        // write your code here
        int l = s.length();
        if (l == 0)
            return 0;
        int f[l + 1];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= l; i++){
            if (s[i - 1] != '0')
                f[i] += f[i - 1];
            if (i >= 2){
                int t = (s[i - 2] - '0')* 10 + s[i - 1] - '0';
                if (t >= 10 && t <= 26)
                    f[i] += f[i - 2];
            }
        }
        return f[l];      
    }    
};

110. Minimum Path Sum

题目链接

题目描述
给定一个只含非负整数的mn网格，找到一条从左上角到右下角的可以使数字和最小的路径。
你在同一时间只能向下或者向右移动一步
*分析**
和机器人走到右下角是一样的。

AC代码

class Solution {
public:
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int>> &a) {
        // write your code here
        int m = a.size();
        int n = a[0].size();
        
        int f[m][n];
        for (int i = 0; i < m; i++){
            
            for (int j = 0; j < n; j++){
                if (i == 0 && j == 0){
                    f[i][j] = a[0][0];
                    continue;
                }
                    
                if (i == 0){
                    f[i][j] = a[i][j] + f[i][j - 1];
                    continue;
                }
                if (j == 0){
                    f[i][j] = a[i][j] + f[i - 1][j];
                    continue;
                }
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + a[i][j];
                
            }
        }
        return f[m - 1][n - 1];
        
    }
};

553. Bomb Enemy

题目链接

题目描述
给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。由于墙比较坚固，所以墙不会被摧毁.

你只能在空的地方放置炸弹.
分析

这题需要好好的分析一下，对于任意一个位置，我们可以认为他的状态f[i][j] 是由上下左右转移而来的。
先分析上
转移方程：

if (i == 0){
    if (a[i][j] == 'E')
        f[i][j] = 1;
else
    f[i][j] = 0;
    res[i][j] += f[i][j];//记录4个方向的和。
    continue;
}
if (a[i][j] == 'E')
    f[i][j] = f[i - 1][j] + 1;
else if (a[i][j] == '0')
    f[i][j] = f[i - 1][j];
else
    f[i][j] = 0; 
res[i][j] += f[i][j];

然后下，左右，就一样了

AC代码

class Solution {
public:
    
    int maxKilledEnemies(vector <vector<char>> &a) {
        int m = a.size();
        if (m == 0)
            return 0;
        int n = a[0].size();
        int res[m][n], f[m][n];
        memset(res, 0, sizeof res);
        // up
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    if (a[i][j] == 'E')
                        f[i][j] = 1;
                    else
                        f[i][j] = 0;
                    res[i][j] += f[i][j];
                    continue;
                }
                if (a[i][j] == 'E')
                    f[i][j] = f[i - 1][j] + 1;
                else if (a[i][j] == '0')
                    f[i][j] = f[i - 1][j];
                else
                    f[i][j] = 0;
                res[i][j] += f[i][j];
            }
        }
        // down
        for (int i = m - 1; i > 0; i--) {
            for (int j = 0; j < n; j++) {
                if (i == m - 1) {
                    if (a[i][j] == 'E')
                        f[i][j] = 1;
                    else
                        f[i][j] = 0;
                    res[i][j] += f[i][j];
                    continue;
                }
                if (a[i][j] == 'E')
                    f[i][j] = f[i + 1][j] + 1;
                else if (a[i][j] == '0')
                    f[i][j] = f[i + 1][j];
                else
                    f[i][j] = 0;

                res[i][j] += f[i][j];
            }
        }
        //left
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    if (a[i][j] == 'E')
                        f[i][j] = 1;
                    else
                        f[i][j] = 0;
                    res[i][j] += f[i][j];
                    continue;
                }
                if (a[i][j] == 'E')
                    f[i][j] = f[i][j - 1] + 1;
                else if (a[i][j] == '0')
                    f[i][j] = f[i][j - 1];
                else
                    f[i][j] = 0;
                res[i][j] += f[i][j];
            }
        }
        //right
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (j == n - 1) {
                    if (a[i][j] == 'E')
                        f[i][j] = 1;
                    else
                        f[i][j] = 0;
                    res[i][j] += f[i][j];
                    continue;
                }
                if (a[i][j] == 'E')
                    f[i][j] = f[i][j + 1] + 1;
                else if (a[i][j] == '0')
                    f[i][j] = f[i][j + 1];
                else
                    f[i][j] = 0;

                res[i][j] += f[i][j];
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == '0')
                    ans = max(ans, res[i][j]);
            }
        }
        return ans;

    }
};

664. Counting Bits

题目链接
题目描述
给出一个非负整数 num，对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示中数字 1 的个数并以数组的形式返回。

分析
二进制嘛，肯定要想到2 。
i与i / 2 的差别就是i比i / 2 多了一位二进制
转移方程就是 f[i] = f[i / 2] | i & 1 == 0; f[i] = f[i / 2] + 1 | i & 1 == 1

AC代码

class Solution {
public:
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    vector<int> countBits(int a) {
        // write your code here
        vector<int> f(a + 1, 0);
        for (int i = 0; i <= a; i++){
            if (i & 1)
                f[i] = f[i / 2] + 1;
            else
                f[i] = f[i / 2];
        }
        return f;
    }
};

516. Paint House II

题目链接

题目描述
这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。

费用通过一个nxk 的矩阵给出，比如cost[0][0]表示房屋0染颜色0的费用，cost[1][2]表示房屋1染颜色2的费用。

所有费用都是正整数

分析
和上面515. Paint House一样就是把3改成n，时间复杂度为m * n * n
但是还有更快的做法：
对于花费矩阵，从第一行到第二行，最优的情况是第二行加上第一行的最小的值，当第一行最小的值得下标之外的第二行，全都加上最小值，等于第一行最小值的下标的加上次小值，就OK了。

当然把这个思路运用到动规里也是可以的，找出上一行的最小值次小值，然后就不用遍历了。

AC代码（动规）

class Solution {
public:
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
     
    int minCostII(vector<vector<int>> &a) {
        int m = a.size();
        if (m == 0)
            return 0;
        int n = a[0].size();
        int f[m + 1][n];
        memset(f[0], 0, sizeof f[0]);
        const int INF = 0x3f3f3f3f;
        for (int i = 1; i <= m; i++){
            for (int j = 0; j < n; j++){
                f[i][j] = INF;
                for (int k = 0; k < n; k++){
                    if (k == j)
                        continue;
                    f[i][j] = min(f[i][j], f[i - 1][k] + a[i - 1][j]);
                }
            }
        }
        int ans = INF;
        for (int i = 0; i < n; i++)
            ans = min(ans, f[m][i]);
        return ans;
    }
};

AC代码（另一种思路）

class Solution {
public:
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
     
    int minCostII(vector<vector<int>> &a) {
        int m = a.size();
        if (!m)
            return 0;
        int n = a[0].size();
        
        int min1 = INT_MAX, min2 = INT_MAX, indx;
        for (int i = 0; i < n; i++){
            if (min1 > a[0][i]){
                min2 = min1;
                min1 = a[0][i];
                indx = i;
            }
            else if (min2 > a[0][i]){
                min2 = a[0][i];
            }
        }
        
        for (int i = 1; i < m; i++){
            for (int j = 0; j < n; j++){
                if (j != indx)
                    a[i][j] += min1;
                else
                    a[i][j] += min2;
            }
            min1 = min2 = INT_MAX;
            for (int j = 0; j < n; j++){
                if (min1 > a[i][j]){
                    min2 = min1;
                    min1 = a[i][j];
                    indx = j;
                }
                else if (min2 > a[i][j]){
                    min2 = a[i][j];
                }
            }
        }
        return min1;
    }
};

AC代码（优化后的动规）

class Solution {
public:
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
     
    int minCostII(vector<vector<int>> &cost) {
        // write your code here
        if (cost.empty() || cost.size() == 0 || cost[0].size() == 0)
            return 0;
        int n = cost.size();
        int m = cost[0].size();
        int f[n + 1][m];
        const int INF = 0x3f3f3f3f;
        memset(f, INF, sizeof f);
        memset(f[0], 0, sizeof f[0]);
        int min1, min2;
        int j1, j2;
        
        for (int i = 1; i <= n; i++){
            min1 = min2 = INF;
            for (int j = 0; j < m; j++){
                if (f[i - 1][j] < min1){
                    min2 = min1;
                    j2 = j1;
                    min1 = f[i - 1][j];
                    j1 = j;
                }
                else if (f[i - 1][j] < min2){
                    min2 = f[i - 1][j];
                    j2 = j;
                }
            }
            for (int j = 0; j < m; j++){
                if (j != j1)
                    f[i][j] = min1 + cost[i - 1][j];
                else
                    f[i][j] = min2 + cost[i - 1][j];
            }
            
        }
        int ans = INF;
        for (int i = 0; i < m; i++)
            ans = min(ans, f[n][i]);
        return ans;
        
    }
};

392. House Robber

题目链接

题目描述
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱，算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱。

分析
因为存在约束，偷与不偷，那就把此约束放在状态里，设0为不偷， 1为偷。
转移方程

1 2	f[i][0] = max(f[i - 1][0], f[i - 1][1]); f[i][1] = f[i - 1][0] + a[i - 1];

但是观察此状态方程，我们可以化简。

because
f[i - 1][0] = max(f[i - 2][0], f[i - 2][1]);
so
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = max(f[i - 2][0], f[i - 2][1]) + a[i - 1];

所以我们完全可以设成一维f[i] 表示在前i个房子中最多能偷多少钱

AC代码

class Solution {
public:
    /**
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &a) {
        // write your code here
        typedef long long ll;
        int n = a.size();
        if (n == 0)
            return 0;
        ll f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; i++){
            if (i == 1)
                f[i] = a[i - 1];
            if (i > 1)
                f[i] = max(f[i - 1], f[i - 2] + a[i - 1]);
        }
        return f[n];
    }
};

534. House Robber II

题目链接

题目描述
在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱，算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱。

这题是House Robber的扩展，只不过是由直线变成了圈

分析
环形dp就是转化成非环形的呗。
对于这一题而言，最后一个和第一个不可能一起选，那就拆成 1 ~ n - 1 和 0 ~ n - 2 。分别dp（写个函数就行）。

AC代码

class Solution {
public:
    /**
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    
    int solve(int st, int en, vector<int> &a){
        int f[en + 1];
        f[st] = 0;
        f[st + 1] = a[st];
        for (int i = st + 2; i <= en; i++){
            f[i] = max(f[i - 1], f[i - 2] + a[i - 1]);
        }
        return f[en];
    }
    
    int houseRobber2(vector<int> &a) {
        int n = a.size();
        if (n == 0)
            return 0;
        if (n == 1)
            return a[0];
            
        return max(solve(0, n - 1, a), solve(1, n, a));
       
    }
};

149. Best Time to Buy and Sell Stock

题目链接

题目描述
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

分析

其实这一题也算不上dp，之所以做着题因为他是铺垫，有两个方法

维护前i个元素的最小值
贪心

AC代码（维护区间最小值）

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &a) {
        // write your code here
        if (a.empty() || !a.size())
            return 0;
        int n = a.size();
        int f[n + 1];
        f[0] = a[0];
        for (int i = 1; i < n; i++){
            if (a[i] < f[i - 1])
                f[i] = a[i];
            else
                f[i] = f[i - 1];
        }
        int m = 0;
        for (int i = n - 1; i >= 1; i--){
            m = max(m, a[i] - f[i - 1]);
        }
        return m;
    }
};

AC代码（贪心）

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &a) {
        int n = a.size();
        if(n == 0 || n == 1)
            return 0;
        int ans = 0, min1 = a[0];
        for (int i = 1; i < n; i++){
            ans = max(ans, a[i] - min1);
            min1 = min(min1, a[i]);
        }
        return ans;
    }
};

150. Best Time to Buy and Sell Stock II

题目链接

题目描述
给定一个数组 prices 表示一支股票每天的价格.

你可以完成任意次数的交易, 不过你不能同时参与多个交易 (也就是说, 如果你已经持有这支股票, 在再次购买之前, 你必须先卖掉它).

设计一个算法求出最大的利润.

分析
这算是个思维题吧，就是只要今天的股票比昨天的股票值钱，就买卖。

AC代码

class Solution {
public:
    int maxProfit(vector<int> &a) {
        int ans = 0;
        for (int i = 1; i < a.size(); i++){
            if (a[i] - a[i - 1] > 0)
                ans += a[i] - a[i - 1];
        }
        
        return ans;
    }
};

151. Best Time to Buy and Sell Stock III

题目链接

题目描述
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

分析
最难的不是只买一次或者说买无数次，而是能买特定的次数。

我们同时将两次拓展到k次，先看两次。

我们有五种状态，分别是 1.第一次股票未买， 2.买第一支股票， 3.卖第一支股票（此时手中无股票）， 4.买第二支股票， 5.卖第二支股票（此时手中无股票）

状态转移：

状态一只能由状态一转换（不盈利）
状态二可以由状态一或者状态二转换（由状态二转换需要盈利，由状态一转换不需要盈利）
状态三能够由状态二转换或者状态三转换（若是由状态二转换能够盈利）
状态四能够由状态二（卖了手中的那支股票然后当天在买一只股票），状态三或者状态四转换（这个比较特殊，若是由状态二转换，则不盈利，若是由状态二或者状态四转换，都要盈利）
状态五可以由状态四或者状态五转换（若是由状态四转换能够盈利）

有人或许会对第2， 4条中的由状态二转化为状态二和状态四化为状态四会盈利感到不解，其实这个盈利是“假盈利”，这是一条链的关系。

怎么理解呢，正常的盈利是卖的股票那一天减买的股票那一天，但是在dp中很难储存你是在那一天买的股票（我这种弱鸡想不到，不过应该会有大佬想到qaq），所以我们采取了这样一条链的方法，我们举个简单的例子。

假如我们第一天就买了一直股票， 就处于阶段二了， 然后我们到第n天才卖出股票， 肉眼观察盈利是 a[n] - a[1]
中间一直处于阶段二， 就是一直处于盈利状态， 
第一天盈利 f[1] = 0
第二天盈利 f[2] = a[2] - a[1] + f[1]
第三天盈利 f[3] = f[2] + a[3] - a[2]
...
第n天盈利 f[n] = f[n - 1] + a[n] - a[n - 1]

我们累加一下就得到f[n] = a[n] - a[1]

这就是巧妙之处

AC代码

class Solution {
public:    
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int> &a) {
        int n = a.size();
        if (n == 0)
            return 0;
        
        int f[n + 1][6];
        memset(f[0], -INF, sizeof f[0]);
        f[0][1] = 0;  //除了f[0][1] 意外其他f[0]都是没有意义的
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= 5; j += 2){ //对于现阶段处于1， 3， 5
                f[i][j] = f[i - 1][j];
                if (i >= 2 && j > 1 && f[i - 1][j - 1] != -INF){
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i - 1] - a[i - 2]);
                }
            }
            for (int j = 2; j <= 5; j += 2){//对于现阶段处于2， 4
                f[i][j] = f[i - 1][j - 1];
                if (i >= 2 && f[i - 1][j] != -INF){
                    f[i][j] = max(f[i][j], f[i - 1][j] + a[i - 1] - a[i - 2]);   
                }
                if (i >= 2 && j >= 3 && f[i - 1][j - 2] != -INF){
                    f[i][j] = max(f[i][j], f[i - 1][j - 2] + a[i - 1] - a[i - 2]);
                }
                
            }
        }
        return max(f[n][1], max(f[n][3], f[n][5]));
        //最后结果一定是从1， 3， 5中取最大值
  
    }
};

393. Best Time to Buy and Sell Stock IV

题目链接

题目大意
给定数组 prices, 其中第 i 个元素代表某只股票在第 i 天第价格.

你最多可以完成 k 笔交易. 问最大的利润是多少?

你不可以同时参与多(k)笔交易(你必须在再次购买前出售掉之前的股票)

分析
就是上一题的升级版，把代码中的5改成 2 * k + 1 即可
当然你若仔细想一下，当k >= n / 2 时可以改成任意次。
这里稍微证明下，显而易见，当 k > n时是可以当成任意次来做的。
首先，我们先思考当股票价格一直上升时，最优策略就是第一天买最后一天卖，所以只需要一次即可。
当股票价格一直下降时，一次也不买卖就是0。
所以我们可以把连续上升的部分只需要一次买，连续下降的部分0次买
所以用的次数最多的情况就是升降升降，也就是n / 2 次。

AC代码

class Solution {
public:
    
    const int INF = 0x3f3f3f3f;
    int maxProfit(int k, vector<int> &a) {
        // write your code here
        if (!k || a.empty() || !a.size())
            return 0;
        int n = a.size();
        if (k >= n / 2){
            int ans = 0;
            for (int i = 1; i < n; i++){
                if (a[i] - a[i - 1] > 0)
                    ans += a[i] - a[i - 1];
            }
            return ans;
        }
        
        int f[n + 1][2 * k + 1 + 1];
        memset(f[0], -INF, sizeof f[0]);
        f[0][1] = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= 2 * k + 1; j += 2){
                f[i][j] = f[i - 1][j];
                if (i > 1 && j > 1 && f[i - 1][j - 1] != -INF)
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i - 1] - a[i - 2]);
            }
            
            for (int j = 2; j <= 2 * k + 1; j += 2){
                f[i][j] = f[i - 1][j  - 1];
                if (i > 1 && f[i - 1][j] != -INF)
                    f[i][j] = max(f[i][j], f[i - 1][j] + a[i -1] - a[i - 2]);
                if (i > 2 && j > 2 && f[i - 1][j - 2] != -INF)
                    f[i][j] = max(f[i][j], f[i - 1][j - 2] + a[i -1] - a[i - 2]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= 2 * k + 1; i += 2)
            ans = max(ans, f[n][i]);
        return ans;
    }
};

76. Longest Increasing Subsequence

题目链接

题目大意
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

分析
就是lis
详情可看此博客：传送门 n方， nlogn，打印路径全都有

AC代码（n方解法）

class Solution {
public:
    
    int longestIncreasingSubsequence(vector<int> &a) {
        int n = a.size();
        if (n == 0)
            return 0;
        // f[i] 代表以a[i] 为结尾的lis的长度
        int f[n + 1];
        f[0] = 1;
        for (int i = 1; i < n; i++){
            f[i] = 1;
            for (int j = 0; j < i; j++){
                if (a[j] < a[i]){
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[i]);
        return ans;
    }
    
};

AC代码nlogn解法

class Solution {
public:
    
    int longestIncreasingSubsequence(vector<int> &a) {
        int n = a.size();
        if (n == 0)
            return 0;
        // f[i] 代表的是 长度为i 的lis的最优解得最后一个数
        int f[n + 1];
        f[0] = 0;
        f[1] = a[0];
        int len = 1;
        
        for (int i = 1; i < n; i++){
            if (a[i] > f[len])
                f[++len] = a[i];
            else{
                int cnt = lower_bound(f + 1, f + len + 1, a[i]) - f;
                f[cnt] = a[i];
            }
        }
        
        return len;
    }
    
};

602. Russian Doll Envelopes

题目链接

题目大意
给一定数量的信封，带有整数对 (w, h) 分别代表信封宽度和高度。一个信封的宽高均大于另一个信封时可以放下另一个信封。
求最大的信封嵌套层数。

分析
俄罗斯套娃问题

二维的简单些

首先先将w 或者 h从小到大排序，然后让另一个变量从大到小（当前面的变量相同时），这样对排序后的第二个变量求一下其lis就行了，为啥要第二个变量从大到小呢，因为要保证求lis时只选一个第一个变量相同的变量

那我们思考一下三维甚至多维的该怎么办呢？（我也是这才有的想法）
我的一个想法是先按照二维的做法，用lis打印路径，保存起来，这就相当于去了两维，重复去就行啦。
然后我们在百度看一看怎么做

AC代码

class Solution {
public:
    typedef pair<int, int> P;
    static bool cmp(P a, P b){
        if (a.first != b.first)
            return a.first < b.first;
        return a.second > b.second;
    }
    
    int maxEnvelopes(vector<pair<int, int>>& a) {
        int n = a.size();
        if (n == 0 || n == 1)
            return n;
        int f[n + 1];
        sort(a.begin(), a.end(), cmp);
        
        f[1] = a[0].second;
        int len = 1;
        
        for (int i = 1; i < n; i++){
            if (a[i].second > f[len])
                f[++len] = a[i].second;
            else
                *lower_bound(f + 1, f + len + 1, a[i].second) = a[i].second;
        }        
        return len;
       
    }
};

513. Perfect Squares

题目大意
题目链接
给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9…)的和等于n。

分析
很容易就分析出来转移方程了。直接看代码吧。
当然这题可以打表找规律优化到O(n) 。
AC代码

class Solution {
public:
    /**
     * @param n: a positive integer
     * @return: An integer
     */
    int numSquares(int n) {
        int f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; i++){
            f[i] = INT_MAX;
            for (int j = 1; j * j <= i; j++){
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }
};

108. Palindrome Partitioning II

题目大意
timulianjie
给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.

最少需要分割几次?

分析
题目中就是求能把s分成最少几个回文子串。
考虑最后一步， s[i … n - 1] 一定是一个回文子串
那就ok了
设f[i] 为前i个字符最少分成多少个回文子串
f[i] = min(f[i], f[j] + 1 | s[j...i - 1] 为回文子串)

现在问题又来了，如何判断 s[j… i - 1]是不是回文子串，那就要预处理了。
回文串的长度只有两种情况，奇数和偶数，我们预预处理，生成一下回文子串即可，详情看代码及注释

AC代码

class Solution {
public:
    /**
     * @param s: A string
     * @return: An integer
     */
    int minCut(string &s) {
        if (s == "")
            return 0;
        int n = s.length();
        bool is[n][n]; // 表示 is[i][j] 表示 s[i..j] 是不是为回文子串
        memset(is, false, sizeof is);
        int i, j;
        for (int k = 0; k < n; k++){
            // 回文串长度为奇数的情况
            i = j = k;
            while(i >= 0 && j < n && s[i] == s[j])
                is[i][j] = true, i--, j++;
            // 回文串长度为偶数的情况
            i = j = k;
            j++;
            while(i >= 0 && j < n && s[i] == s[j])
                is[i][j] = true, i--, j++;
        }
        int f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; i++){
            f[i] = INT_MAX;
            for (int j = 0; j < i; j++){
                if (is[j][i - 1])
                    f[i] = min(f[i], f[j] + 1);
            }
        }
        // 最后减一是因为题目中问的是最少切几刀， f[n] 表示的是最少切成多少个回文子串
        return f[n] - 1; 
    }
};

437. Copy Books

题目大意
题目链接
给定 n 本书, 第 i 本书的页数为 pages[i]. 现在有 k 个人来复印这些书籍, 而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages[0], pages[1], pages[2], 但是不可以只复印 pages[0], pages[2], pages[3] 而不复印 pages[1].

所有人复印的速度是一样的, 复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?

返回完成复印任务最少需要的分钟数.

分析

dp做法：设 f[k][i] 为 k个人复印前i本书所需要的最短时间。
二分做法：二分最大值与和，找出满足条件的数。

AC代码（DP）

class Solution {
public:
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */

   
    int copyBooks(vector<int> &a, int K) {
        if(a.size() == 0)
            return 0;
        
        int n = a.size();
        int f[K + 1][n + 1];
        f[1][0] = 0;
        for (int i = 1; i <= n; i++)
            f[1][i] = f[1][i - 1] + a[i - 1];
        
        for (int k = 2; k <= K; k++){
            for (int i = 1; i <= n; i++){
                f[k][i] = INT_MAX;
                for (int j = 1; j <= i; j++){
                    f[k][i] = min(f[k][i], max(f[k - 1][j], f[1][i] - f[1][j]));
                }
            }
        }
        return f[K][n];
       
    }
};

AC代码（二分）

class Solution {
public:
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */

   
    bool check(int n, int m, vector<int> a, int k){
        int res = 1, sum = 0;
        for (int i = 0; i < n; i++){
            if (sum + a[i] <= m)
                sum += a[i];
            else
                sum = a[i], res++;
        }
        return res <= k;
        
        
    }
    
    int copyBooks(vector<int> &a, int K) {
        if(a.size() == 0)
            return 0;
        int n = a.size();
        int ans = 0, sum = 0;
        for (int i = 0; i < n; i++){
            sum += a[i];
            ans = max(ans, a[i]);
        }
        int low = ans, high = sum;
        int m;
        while(low < high){
            m = low + (high - low) / 2;
            if (check(n, m, a, K))
                high = m;
            else
                low = m + 1;
        }
        return low;
        
        
    }
};

394. Coins in a Line

题目大意
题目链接
有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定先手玩家必胜还是必败?

分析

AC代码

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        if(n == 0)
            return false;
        int f[n + 1];
        f[0] = false;
        f[1] = f[2] = true;
        for (int i = 3; i <= n; i++){
            if (f[i - 1] && f[i - 2])
                f[i] = false;
            else
                f[i] = true;
        }
        return f[n];
        
    }
};

找到规律后更简单的写法

    class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        // write your code here
        if (n % 3 != 0)
            return true;
        return false;
    }
};

92. Backpack

题目大意
题目链接
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]（每个物品只能选一件）

分析
背包，设f[i][j] 为前i件物品，能不能装满j

AC代码

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> &a) {
        int n = a.size();
        if (!n || !m)
            return 0;
        int f[n + 1][m + 1];
        memset(f, false, sizeof f);
        f[0][0] = true;
        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= m; j++){
                f[i][j] = f[i - 1][j];
                
                if (j >= a[i - 1])  // j 能不能由 a[i - 1] 和 j - a[i - 1] 组成
                    f[i][j] = f[i][j] | f[i - 1][j - a[i - 1]];
            }
        }
        for (int i = m; i >= 0; i--)
            if (f[n][i])
                return i;
              
    }
};

由上面转移方程可知
f[i][j] 是由 f[i - 1][j] 和 f[i - 1][j - a[i - 1]转移
所以用一维即可

AC代码

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> &a) {
        int n = a.size();
        if (!n || !m)
            return 0;
        int f[m  + 1];
        memset(f, false, sizeof f);
        f[0] = true;
        for (int i = 1; i <= n; i++){
            for (int j = m; j >= a[i - 1]; j--){
                f[j] = f[j] | f[j - a[i - 1]];
            }
        }
        for (int i = m; i >= 0; i--)
            if (f[i]) return i;
    }
};

564. Combination Sum IV

题目大意
题目链接
给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。

一个数可以在组合中出现多次。
数的顺序不同则会被认为是不同的组合。

分析
转移方程很好想，具体看AC代码吧。

AC代码

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    int backPackVI(vector<int> &a, int W) {
        if(W == 0)
            return 0;
        int f[W + 1];
        int n = a.size();
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= W; i++){
            for (int j = 0; j < n; j++){
                if (i >= a[j])
                    f[i] += f[i - a[j]];
            }
        }
        return f[W];
    }
};

563. Backpack V

题目大意
题目链接

给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次

分析
f[i][j] 表示用前i个物品拼出重量j 的方案数
f[i][j] = f[i - 1][j] + f[i - 1][j - a[i - 1]]
然后可以优化成一维数组，如何优化看上面两题

AC代码
二维数组

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    int backPackV(vector<int> &a, int W) {
        int n = a.size();
        if (n == 0)
            return 0;
        
        int f[n + 1][W + 1];
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        
        for (int i = 1; i <= n; i++){
            
            for (int j = 0; j <= W; j++){
                f[i][j] = f[i - 1][j];
                if (j >= a[i - 1])
                    f[i][j] += f[i - 1][j - a[i - 1]];
            }
        }
        
        return f[n][W];
    }
};

一维数组

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    int backPackV(vector<int> &a, int W) {
        int n = a.size();
        if (n == 0)
            return 0;
        
        int f[W + 1];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = W; j >= 0; j--){
                if (j >= a[i - 1])
                    f[j] += f[j - a[i - 1]];
            }
        }
        
        return f[W];
        
        
    }
};

125. Backpack II

题目大意
题目链接
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

分析
f[i][j] 表示前i件物品重量为j的最大价值
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i - 1]] + v[i - 1])
化简为一位数组也是一样

AC代码
二维

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int W, vector<int> &w, vector<int> &v) {
        int n = w.size();
        if (!n)
            return 0;
        int f[n + 1][W + 1];
        memset(f[0], 0 , sizeof f[0]);
        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= W; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= w[i - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
        return f[n][W];
        
    }
        
};

一维

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int W, vector<int> &w, vector<int> &v) {
        int n = w.size();
        if (!n)
            return 0;
        int f[W + 1];
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i++){
            for (int j = W; j >= w[i - 1]; --j) {
                f[j] = max(f[j], f[j - w[i - 1]] + v[i - 1]);
            }
        }
        return f[W];
        
    }
        
};

667. Longest Palindromic Subsequence

题目描述
题目链接
给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.

分析

最优策略产生最长回文子串T， 长度为M
情况1: 回文串长度是1， 即一个字母
情况2： 回文串长度大于1， 那么必有T[0] = T[M - 1]

设T[0]是S[i], T[M - 1]是S[j]
那么T剩下的部分T[1...M - 2]仍然是一个回文串， 而且是S[i + 1 ... j - 1]的最长回文子序列
要求S[i..j]s的最长回文子序列
如果S[i] = S[j]， 需要知道S[i + 1 ... j - 1] 的最长回文子序列
否则答案就是S[i + 1 ... j] 的最长回文子序列或者S[i ... j - 1]的最长回文子序列的最大值
设 f[i][j] 为S[i ... j] 的最长回文子序列的长度
f[i][j] = max(f[i + 1][j], f[i][j + 1], f[i + 1][j - 1]  +2 | S[i] == S[j])

这题我用记忆化搜索写下， dp也写

AC代码
记忆化搜索

class Solution {
public:
    string s;
    int f[1003][1003];
    void _(int l, int r){
        if (f[l][r] != -1)
            return ;
        if (l == r){
            f[l][r] = 1;
            return ;
        }
            
        if (l + 1 == r){
            f[l][r] = (s[l] == s[r]) ? 2 : 1;
            return;
        }
            
        _(l + 1, r);
        _(l, r - 1);
        _(l + 1, r - 1);
        f[l][r] = max(f[l + 1][r], f[l][r - 1]);
        if (s[l] == s[r])
            f[l][r] = max(f[l][r], f[l + 1][r - 1] + 2);
                
    }
    
    int longestPalindromeSubseq(string &ss) {
        s = ss;
        int n = s.length();
        if (n == 0 || n == 1)
            return n;
        memset(f, -1, sizeof f);
        _(0, n - 1);
        return f[0][n - 1];
        
    }
};

class Solution {
public:
    
    
    int longestPalindromeSubseq(string &s) {
        int n = s.length();
        if (n == 0 || n == 1)
            return n;
        int f[1003][1003];
        for (int l = 0; l < n; ++l){
            for (int i = 0; i < n; i++){
                int j = i + l;
                if (l == 0){
                    f[i][j] = 1;
                    continue;
                }
                if (l == 1){
                    f[i][j] = s[i] == s[j] ? 2 : 1;
                    continue;
                }
                f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                
                if (s[i] == s[j]){
                    f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
                }
                
            }
        }
        return f[0][n - 1];
        
        
    }
};

396. Coins In A Line III

题目大意
题目链接
• 题意：
• 给定一个序列a[0], a[1], …, a[N-1]
• 两个玩家Alice和Bob轮流取数
• 每个人每次只能取第一个数或最后一个数
• 双方都用最优策略，使得自己的数字和尽量比对手大
• 问先手是否必胜
– 如果数字和一样，也算先手胜

分析

• 这题是一道博弈题，目标是让自己拿到的数字之和不比对手小
• 设己方数字和是A，对手数字和是B，即目标是A>=B
• 等价于A-B>=0
• 也就是说，如果Alice和Bob都存着自己的数字和与对手的数字和之差，
分别记为SA=A-B，SB=B-A
• 则Alice的目标是最大化SA，Bob的目标是最大化SB
• 当一方X面对剩下的数字，可以认为X就是当前的先手，他的目标就是最
大化SX=X-Y
• 当他取走一个数字m后，对手Y变成先手，同理他也要最大化SY=Y-X
• 对于X来说，SX = -SY + m
• 其中，m是当前这步的数字，-SY是对手看来的数字差取相反数（因为先手是X）
• 现在X有两种选择，取第一个数字m1或最后一个数字m2，为了最大化SX，
应该选择较大的那个SX
• 如果Alice第一步取走a[0]，Bob面对a[1..N-1]
• Bob的最大数字差是SY
• Alice的数字差是a[0]-SY
• 如果Alice第一步取走a[N-1]，Bob面对a[0..N-2]
• Bob的最大数字差是S’-Y
• Alice的数字差是a[N-1]-S’-Y
• Alice选择较大的数字差
• 当Bob面对a[1..N-1]，他这时是先手
• 他的目标同样是最大化先手（自己）和后手（Alice）的数字差
• 但是此时的数字少了一个：a[1..N-1]
• 子问题
• 状态：设f[i][j]为一方先手在面对a[i..j]这些数字时，能得到的最大的与对手的数字差
设f[i][j]为一方在面对a[i..j]这些数字时，能得到的最大的与对手的数字差
f[i][j] = max{a[i] - f[i+1][j], a[j] - f[i][j-1]}
为一方在面对a[i..j]时，
能得到的最大的与对
手的数字差

选择a[i]，对手采取最优策
略时自己能得到的最大的
与对手的数字差

选择a[j]，对手采取最优
策略时自己能得到的最
大的与对手的数字差

• 设f[i][j]为一方在面对a[i..j]这些数字时，能得到的最大的与对手的数字差
• f[i][j] = max{a[i]-f[i+1][j], a[j]-f[i][j-1]}
• 只有一个数字a[i]时，己方得a[
• 长度1：f[0][0], f[1][1], f[2][2], …, f[N-1][N-1]
• 长度2： f[0][1], …, f[N-2][N-1]
• …
• 长度N： f[0][N-1]
• 如果f[0][N-1]>=0，先手Alice必赢，否则必输
• 时间复杂度O(N2)，空间复杂度O(N2)

AC代码

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &a) {
        // write your code here
        if (a.empty())
            return true;
        int n = a.size();
        int f[n][n];
        int i, j;
        for (i = 0; i < n; i++){
            f[i][i] = a[i];
        }
        for (int len = 1; len < n; len++){
            i = 0, j = len;
            while(j < n){
                f[i][j] = max(a[j] - f[i][j - 1], a[i] - f[i + 1][j]);
                i++, j++;
                
            }
            
        }
        return f[0][n - 1] >= 0;
        
        
    }
};

430. Scramble String

题目大意

题目链接

给定一个字符串 s1, 将其递归地分割成两个非空子字符串, 然后可以得到一棵二叉树.

下面是 s1 = "great" 可能得到的一棵二叉树:

      great
     /    \
    gr    eat
   / \    /  \
  g   r  e   at
             / \
            a   t
在攀爬字符串的过程中, 我们可以选择其中任意一个非叶节点, 交换该节点的两个子节点.

例如，我们选择了 "gr" 节点, 并将该节点的两个子节点进行交换, 并且将祖先节点对应的子串部分也交换, 最终得到了 "rgeat". 我们认为 "rgeat" 是 "great" 的一个攀爬字符串.

      rgeat
     /    \
    rg    eat
   / \    /  \
  r   g  e   at
             / \
            a   t
类似地, 如果我们继续将其节点 "eat" 和 "at" 的子节点交换, 又可以得到 "great" 的一个攀爬字符串 "rgtae".

     rgtae
     /    \
    rg    tae
   / \    /  \
  r   g  ta   e
         / \
        t   a
给定两个相同长度的字符串 s1 和 s2，判断 s2 是否为 s1 的攀爬字符串.

你可以从任何一棵 s1 可以构造出的二叉树开始攀爬, 但是在攀爬得到 s2 的过程中不能重新构造二叉树.

分析

• 显然，T如果长度和S不一样，那么肯定不能由S变换而来
• 如果T是S变换而来的，并且我们知道S最上层二分被分成S=S1 S2，那么
一定有：
– T也有两部分T=T1 T2，T1是S1变换而来的，T2是S2变换而来的
– T也有两部分T=T1 T2，T1是S2变换而来的，T2是S1变换而来的

• 要求T是否由S变换而来
• 需要知道T1是否由S1变换而来的，T2是否由S2变换而来
• 需要知道T1是否由S2变换而来的，T2是否由S1变换而来
• S1, S2, T1, T2长度更短
• 子问题
• 状态：f[i][j][k][h]表示T[k..h]是否由S[i..j]变换而来
• 这里所有串都是S和T的子串，且长度一样
• 所以每个串都可以用(起始位置，长度)表示
• 例如：
– S1长度是5，在S中位置7开始
– T1长度是5，在T中位置0开始
– 可以用f[7][0][5]=True/False表示S1能否通过变换成为T1
• 状态：设f[i][j][k]表示S1能否通过变换成为T1
– S1为S从字符i开始的长度为k的子串
– T1为T从字符j开始的长度为k的子串
• 设f[i][j][k]表示S1能否通过变换成为T1
– S1为S从字符i开始的长度为k的子串
– T1为T从字符j开始的长度为k的子串
f[i][j][k] = OR1<=w<=k-1{f[i][j][w] AND f[i+w][j+w][k-w]}
OR
1<=w<=k-1{f[i][j+k-w][w] AND f[i+w][j][k-w]}

AC代码

class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: Another string
     * @return: whether s2 is a scrambled string of s1
     */
    bool isScramble(string &s1, string &s2) {
        // write your code here
        int n = s1.length();
        bool f[n][n][n + 1];

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                f[i][j][1] = (s1[i] == s2[j]);
        
        for (int k = 2; k <= n; ++k){
            for (int i = 0; i <= n - k; ++i){
                for (int j = 0; j <= n - k; ++j){
                    f[i][j][k] = false;
                    for (int w = 1; w < k; ++w){
                        if (f[i][j][w] && f[i + w][j + w][k - w]){
                            f[i][j][k] = true;
                            break;
                        }
                        if (f[i][j + k - w][w] && f[i + w][j][k - w]){
                            f[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }
        return f[0][0][n];
    }
};

168. Burst Balloons

题目大意
题目链接
有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。

你可以假设nums[-1] = nums[n] = 1。-1和n位置上的气球不真实存在，因此不能吹爆它们。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

分析

• 所有N个气球都被扎破
• 最后一步：一定有最后一个被扎破的气球，编号是i
• 扎破i时，左边是气球0，右边是气球N+1，获得金币1*ai*1=ai
• 此时气球1~i-1以及i+1~N都已经被扎破，并且已经获得对应金币
• 要求扎破1~N号气球，最多获得的金币数
• 需要知道扎破1~i-1号气球，最多获得的金币数和扎破i+1~N号气球，最
多获得的金币数
• 子问题
• 状态：设f[i][j]为扎破i+1~j-1号气球，最多获得的金币数
• 设f[i][j]为扎破i+1~j-1号气球，最多获得的金币数
– i和j不能扎破
f[i][j] = maxi<k<j{f[i][k] + f[k][j] + a[i] * a[k] * a[j]}

AC代码

class Solution {
public:
    /**
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
     
     
    int maxCoins(vector<int> &aa) {
        // write your code here
        int n = aa.size();
        vector<int>a;
        a.push_back(1);
        for (int i = 0; i < n; ++i){
            a.push_back(aa[i]);
        }
        a.push_back(1);
        int f[n + 2][n + 2];
        memset(f, 0, sizeof f);
 
        int i, j;
        for (int l = 2; l <= n + 1; ++l){
            for (i = 0; i <= n; ++i){
                j = i + l;
                if (j > n + 1)
                    break;
                for (int k = i + 1; k < j; k++)
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k]);
            }
        }
        
        return f[0][n + 1];
        
    }
};

77. Longest Common Subsequence

题目大意
题目链接
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

分析

• 设A长度是m, B长度是n
• 现在我们考虑最优策略产生出的最长公共子串（虽然还不知道是什么）
• 最后一步：观察A[m-1]和B[n-1]这两个字符是否作为一个对子在最优策
略中
• 最长公共子串也是公共子串：长度是L选定了L个对应的对子

情况一：对子中没有A[m-1]
推论：A和B的最长公共子串就是A前m-1个字符和B前n个字符的最长公共子串
情况二：对子中没有B[n-1]
推论：A和B的最长公共子串就是A前m个字符和B前n-1个字符的最长公共子串
情况三：对子中有A[m-1]-B[n-1]
推论：A和B的最长公共子串就是A前m-1个字符和B前n-1个字符的最长公共子串+A[m-1]
• 状态：设f[i][j]为A前i个字符A[0..i-1]和B前j个字符[0..j-1]的最长公共子串
的长度
• 设f[i][j]为A前i个字符A[0..i-1]和B前j个字符[0..j-1]的最长公共子串的长度
• 要求f[m][n]
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1|A[i-1]=B[j-1]}

AC代码

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &a, string &b) {
        // write your code here
        int n = a.length();
        int m = b.length();
        int f[n + 1][m + 1];

        
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= m; j++){
                if (i == 0 || j == 0){
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (a[i - 1] == b[j - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return f[n][m];

    }
};

29. Interleaving String

题目大意
题目大意
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成

分析

• 首先，如果X的长度不等于A的长度+B的长度，直接输出False
• 设A长度是m, B长度是n，X的长度是m+n
• 最后一步：假设X是由A和B交错形成的，那么X的最后一个字符X[m+n-1]
– 要么是A[m-1]
• 那么X[0..m+n-2]是由A[0..m-2]和B[0..n-1]交错形成的
– 要么是B[n-1]
• 那么X[0..m+n-2]是由A[0..m-1]和B[0..n-2]交错形成的
• 要求X[0..m+n-1]是否由A[0..m-1]和B[0..n-1]交错形成
• 需要知道X[0..m+n-2]是否由A[0..m-2]和B[0..n-1]交错形成，以及
X[0..m+n-2]是否由A[0..m-1]和B[0..n-2]交错形成
• 子问题
• 状态：设f[s][i][j]为X前s个字符是否由A前i个字符A[0..i-1]和B前j个字符
B[0..j-1]交错形成
• 但是s=i+j，所以可以简化为：设f[i][j]为X前i+j个字符是否由A前i个字符
A[0..i-1]和B前j个字符B[0..j-1]交错形成
• 设f[i][j]为X前i+j个字符是否由A前i个字符A[0..i-1]和B前j个字符B[0..j-1]交错
形成
f[i][j] = (f[i-1][j] AND X[i+j-1]==A[i-1]) OR (f[i][j-1] AND X[i+j-1]==B[j-1])

AC代码

class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
    bool isInterleave(string &s1, string &s2, string &s3) {
        // write your code here
        int n = s1.length();
        int m = s2.length();
        bool f[n + 1][m + 1];
        if (s3.length() != n + m)
            return false;
        for (int i = 0; i <= n; ++i){
            for (int j = 0; j <= m; ++j){
                if (i == 0 && j == 0){
                    f[i][j] = true;
                    continue;
                }
                
                f[i][j] = false;
                if (i > 0 && s1[i - 1] == s3[i + j - 1])
                    f[i][j] |= f[i - 1][j];
                if (j > 0 && s2[j - 1] == s3[i + j - 1])
                    f[i][j] |= f[i][j - 1];
            }
        }
        
        
        return f[n][m];
        
        
        
    }
};

119. Edit Distance

题目描述
题目链接
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。

分析

1
2
3

• 设f[i][j]为B前j个字符B[0..j-1]在A前i个字符A[0..i-1]中出现多少次
• 要求f[m][n]
f[i][j] = f[i-1][j-1]|A[i-1]=B[j-1] + f[i-1][j]

AC代码

class Solution {
public:
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    int minDistance(string &s1, string &s2) {
        // write your code here
        if (s1 == s2)
            return 0;
        int n = s1.length();
        int m = s2.length();
        int f[n + 1][m + 1];
        for (int i = 0; i <= n; ++i){
            for (int j = 0; j <= m; ++j){
                if (i == 0 || j == 0){
                    f[i][j] = max(i, j);
                    continue;
                }
                
                if (s1[i - 1] == s2[j - 1]){
                    f[i][j] = f[i - 1][j - 1];
                    continue;
                }
                
                f[i][j] = min(f[i - 1][j], min(f[i - 1][j - 1], f[i][j - 1])) + 1;
                
            }
        }
        
        
        return f[n][m];
        
    }
};

118. Distinct Subsequences

题目大意
题目链接
给定字符串 S 和 T, 计算 S 的所有子序列中有多少个 T.

子序列字符串是原始字符串删除一些(或零个)字符之后得到的字符串, 并且要求剩下的字符的相对位置不能改变. (比如 “ACE” 是 ABCDE 的一个子序列, 而 “AEC” 不是)

分析

• 双序列型动态规划
• B在A中出现多少次（可以不连续）
• 如果至少出现一次，那么A和B的最长公共子串就是B，而且也不能更长
• 用最长公共子串的思路：对应对子
• 状态：设f[i][j]为B前j个字符B[0..j-1]在A前i个字符A[0..i-1]中出现多少次
• 设f[i][j]为B前j个字符B[0..j-1]在A前i个字符A[0..i-1]中出现多少次
• 要求f[m][n]
f[i][j] = f[i-1][j-1]|A[i-1]=B[j-1] + f[i-1][j]

AC代码

class Solution {
public:
    /**
     * @param S: A string
     * @param T: A string
     * @return: Count the number of distinct subsequences
     */
    int numDistinct(string &s, string &t) {
        // write your code here
        int m = s.length();
        int n = t.length();
        
        int f[m + 1][n + 1];
        for (int i = 0; i <= m; i++){
            for (int j = 0; j <= n; j++){
                if (j == 0){
                    f[i][j] = 1; 
                    continue;
                }
                if (i == 0){
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1])
                    f[i][j] += f[i - 1][j - 1];
                
            }
        }
        
        return f[m][n];
        
    }
};

1	恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞，我的心为你悸动不休。 --mingfuyan