第一章-动态规划

动态规划求解模式

动态规划具备了一下三个特点：
1、把原来的问题分解成了几个相似子问题
2、所有的子问题只需要解决一次
3、储存子问题的解
从以下四个角度考虑：
1、初始状态定义
2、状态间转移方程
3、状态的初始化
4、返回结果
解决问题主要适用于：查找最优解，最大值/最小值，可不可行，是不是，方案个数

例1 斐波那契数列

牛客网:
https://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3

动态规划解法

class Solution {
public:
    int Fibonacci(int n) {
        vector<int> ret(n + 1, 0);
        //初始状态
        ret[1] = ret[2] = 1;
        //递推公式
        //ret[i] = ret [i - 1] + ret[i - 2];
        for(int i = 3; i <= n; i++)
        {
            ret[i] = ret[i - 1] + ret[i - 2];
        }
        return ret[n];
    }
};

例2 变态青蛙跳台阶

牛客网：
https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387

问题分析

定义状态

跳上i级台阶的方法数

状态转移方程

分解：
一次跳1级台阶：1， F(i - 1)
一次跳2级台阶：2， F(i - 2)
……
推得状态转移方程：
F(i) = F(i - 1) + F(i - 2) + … + F(1)
F(i - 1) = F(i - 2) + F(i - 3) + … + F(1)
F(i) = F(i - 1) + F(i - 1) = 2 * F(i - 1);

初始状态和最终状态

F(1) = 1,求F(n)。

实现

class Solution {
public:
    int jumpFloorII(int number) {
        //初始状态
        int f1 = 1;
        //状态转移方程：F(i) = 2 * F(i - 1)
        for(int i = 2; i <= number; i++)
        {
            f1 = 2 * f1;
        }
        return f1;
    }
};

优化

根据状态转移方程我们可以得知，F(n) = 2 ^ (n - 1);所以可以得到优化：

class Solution {
public:
    int jumpFloorII(int number) {
        return (1 << (number - 1));
    }
};

例3 求连续最大子数组的和

牛客网：

https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484

分析

定义状态

到此项为止前i项的连续子序列的最大和

状态转移方程

F(i) = max(F(i - 1) + a[i], a[i]);

初始状态和最终状态

初始状态F[0] = a[0]。
最终结果max(F[i])。

实现

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
        {
            return 0;
        }
        vector<int> ret(array.size(), 0);
        //初始状态
        ret[0] = array[0];
        //状态转移
        for(int i = 1; i < array.size(); i++)
        {
            ret[i] = max(array[i] + ret[i - 1], array[i]);
        }
        //求max(F[i])
        int maxNum = ret[0];
        for(int i = 0; i < ret.size(); i++)
        {
            maxNum = max(maxNum, ret[i]);
        }
        return maxNum;
    }
};

例4 word-break(字符串分割)

牛客网：
https://www.nowcoder.com/questionTerminal/5f3b7bf611764c8ba7868f3ed40d6b2c

分析

定义状态

F(i)：前i个字符能否被分割。

状态转移方程

F(i): F(i)能否被分割取决于前j项能否被分割和j + 1到第i项能否被分割。（此处j取0 ~ i - 1）
得递推方程F(i) : F(j) && (j + 1 ~ i)能否被分割

初始状态和最终状态

初始状态：F(0) = true。
最终状态F(n)。

实现

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.empty() || dict.empty())
        {
            return false;
        }
        vector<bool> Fn(s.size() + 1, false);
        //初始状态
        Fn[0] = true;
        for(int i = 1; i <= s.size(); i++)
        {
            //状态转移
            //F(i) = F(j) && (j + 1 ~ i), (0 <= j < i)能否被分割
            for(int j = i - 1; j >= 0; j--)
            {
                if(Fn[j] && dict.find(s.substr(j, i - j)) != dict.end())
                {
                    Fn[i] = true;
                    break;
                }
            }
        }
        //最终状态
        return Fn[s.size()];
    }
};

例5 triangle(三角矩阵最短路)

牛客网：
https://www.nowcoder.com/questionTerminal/2b7995aa4f7949d99674d975489cb7da

分析

定义状态

F[i][j]: 从(0, 0)到(i, j)的最短路径和。

状态转移方程

一般情况下，走到每个位置的最短路径都可以看作是上一行相邻两个位置的最短路径+这个位置的路径长度，数学描述：F[i][j]:min(F[i - 1][j], F[i - 1][j - 1]) + a[i][j]。
但要考虑边界状态：当在矩阵边缘时只有一种选择的情况，即F[i][0] = F[i - 1][0];F[i][i] = F[i - 1][i - 1]。

初始状态和最终状态

初始状态：F[0][0] = a[0][0]。
最终状态：min(F[n - 1][j])，即最后一行中的最小值。

实现

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty())
        {
            return 0;
        }
        //初始状态
        vector<vector<int>> ret(triangle);
        //状态转移
        int row = ret.size();
        for(int i = 1; i < row; ++i)
        {
            ret[i][0] = ret[i - 1][0] + triangle[i][0];
        }
        for(int i = 1; i < row; ++i)
        {
            ret[i][i] = ret[i - 1][i - 1] + triangle[i][i];
        }
        for(int i = 1; i < row; ++i)
        {
            for(int j = 1; j < i; ++j)
            {
                ret[i][j] = min(ret[i - 1][j], ret[i - 1][j - 1]) + triangle[i][j];
            }
        }
        //最终状态
        int minSum = ret[row - 1][0];
        for(int i = 1; i < row; i++)
        {
            minSum = min(minSum, ret[row - 1][i]);
        }
        return minSum;
    }
};

例6 求路径数量

牛客网：
https://www.nowcoder.com/questionTerminal/3cdf08dd4e974260921b712f0a5c8752

分析

状态定义

F[i][j]：从左上角到达下标(i, j)的路径总数

状态转移方程

if(a[i][j] == 1) F[i][j] = 0;
if(a[i][j] == 0) F[i][j] = F[i][j - 1] + F[i - 1][j]。

初始状态和最终状态

初始状态：如果第一行第一列有障碍物表示这条路走不通则路径数置0，否则只有一条路径，置一if(a[0][j]) == 1) F[0][j] = 0，if(a[i][0] == 1) F[i][0] = 0，这种情况下这条路走不通。
最终状态：F[i][j]。

实现

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        if(obstacleGrid.empty())
        {
            return 0;
        }
        if(obstacleGrid[0][0] == 1)
        {
            return 0;
        }
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        vector<vector<int>> pathNum(row, vector<int>(col, 0));
        for(int i = 0; i < row; i++)
        {
            if(obstacleGrid[i][0] == 1)
            {
                break;
            }
            else
            {
                pathNum[i][0] = 1;
            }
        }
        for(int i = 0; i < col; i++)
        {
            if(obstacleGrid[0][i] == 1)
            {
                break;
            }
            else 
            {
                pathNum[0][i] = 1;
            }
        }
        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                if(obstacleGrid[i][j] == 1)
                {
                    pathNum[i][j] = 0;
                }
                else
                {
                    pathNum[i][j] = pathNum[i][j - 1] + pathNum[i - 1][j];
                }
            }
        }
        return pathNum[row - 1][col - 1];
    }
};

例7 背包问题

lintcode：
https://www.lintcode.com/problem/backpack-ii/description

分析

背包问题是一类问题，主要是求解约束条件下的最优解问题。

状态定义

F[i][j]：前i个商品，包的重量为j的最大价值。定义二维数组遍历所有商品，和到当前商品情况下背包容量从0 - max的所有情况下的最大值求解，遍历到最后则可得到n个全部商品情况下背包最大容量max下背包可拿的最大价值F[n][max]。

状态转移方程

当前商品空间大于包能承受的总空间，放不下直接跳过。数学描述：if(w[i] > j) F[i][j] = F[i - 1][j]。
当前商品空间小于等于包能承受总空间，可以选择放可以选择不放，如果不放入，则F[i][j] = F[i - 1][j]；如果放入，则当前重量等于遍历到的上一个商品并且空间还有w[i]这么大的时候的价值+本商品的价值，最大价值F[i][j] = F[i - 1][j - w[i]] + v[i]，选择放入或不放入商品情况中的最大值作为最优解。数学描述：if(w[i] <= j) max(F[i - 1][j], F[i - 1][j - w[i]] + v[i]);

初始状态和最终状态

初始状态：没有商品时，F[0][j] = 0,最大容量为0时F[i][0] = 0。
最终状态：遍历完全部n个商品，并且背包总容量为最大值m时得到最大价值F[n][m]。

实现

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 m, vector<int> &A, vector<int> &V) {
        if(A.empty())
        {
            return 0;
        }
        int row = A.size();
        vector<vector<int>> maxValue(row + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= row; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                if(A[i - 1] > j)
                {
                    maxValue[i][j] = maxValue[i - 1][j];
                }
                else
                {
                    maxValue[i][j] = max(maxValue[i - 1][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        return maxValue[row][m];
    }
};