LeetCode：动态规划（二）

接着上一篇博客，这里主要是记录一下我在刷的LeetCode上难度为medium的动态规划的题目。

例题7、最长上升子序列 LeetCode 300

给定一个未排序的整型数组，返回最长上升子序列的长度。

1
2
3

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

我们定义一个dp数组，数组长度输入数组nums长度相同。假设dp[i]表示前i个数以A[i]结尾的最长上升子序列长度。就拿nums=[10,9,2,5,3,7,101,18]举例。
前0个数，以nums[0]=10结尾，只有一个数，dp[0]=1;
前1个数，以nums1=9 结尾，其前面没有比9小的数，dp1=1;
前2个数，以nums2=2 结尾，其前面没有比2小的数，dp2=1;
前3个数，以nums3=5 结尾，其前面比5小的数有2，dp3=1+dp2=2;
前4个数，以nums4=3 结尾，其前面比3小的数有2，dp4=1+dp2=2;
前5个数，以nums5=7 结尾，其前面比7小的数有2,5,3，dp5=1+max(dp2,dp3,dp4)+1=3;
前6个数，以nums[6]=101结尾，其前面比101小的数有10,9,2,5,3,7，dp[6]=1+max(dp[0],dp1,dp2,dp3,dp4,dp5)+1=4;
前7个数，以nums[7]=18结尾，其前面比18小的数有10,9,2,5,3,7，dp[7]=1+max(dp[0],dp1,dp2,dp3,dp4,dp5)+1=4;
所以最长的上升子序列的长度为max(dp[i])=4;
因此，可以得到其状态转移方程为：

$dp[i]=max(dp[j]+1),0<=j<i,arr[j]<arr[i]$

代码实现如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()<=0)return 0;
        vector<int>dp(nums.size(),1);
        for(int i=0;i<nums.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])
                {
                    dp[i]=std::max(dp[i],dp[j]+1);
                }
            }
        }
        vector<int>::iterator p = max_element(dp.begin(), dp.end());
        return *p;
    }
};

如果对这道题进行修改，最长递增子序列有且只有一个，求最长递增子序列长度，并返回最长递增子序列。那我们应该怎么做呢？假设nums=[2,1,5,3,6,4,8,9,7],求出数组dp=[1,1,2,2,3,3,4,5,4]。那如何返回最长递增子序列呢。
（1）遍历dp数组，找到最大值以及位置。在本例中，最大值为5，位置为7，说明最终的最长递增子序列的长度为5，并以nums[7] 这个数nums[7]=9 结尾。
（2）从nums数组位置7开始从右遍历，如果对于某一位置i，有 nums[i]<nums[7] && dp[7]=dp[i]+1 ，说明nums[i]可以作为最长递增子序列的倒数第二个数，在本例中nums[6]<nums[7],并且有dp[7]=dp[6]+1，所以8可以作为最长递增子序列的倒数第二位数。
（3）重复（2）过程就可以找到最长上升子序列的所有数。

vector<int>generateDP(const vector<int>&nums)//生成dp数组
{
	vector<int>dp(nums.size(), 1);
	if (nums.size() <= 0)return dp;
	for (int i = 0; i<nums.size(); i++)
	{
		for (int j = 0; j<i; j++)
		{
			if (nums[j]<nums[i])
			{
				dp[i] = std::max(dp[i], dp[j] + 1);
			}
		}
	}
	return dp;
}
vector<int>generateLIS(const vector<int>&nums, vector<int>dp)//生成最长上升子序列
{
	vector<int>::iterator p = max_element(dp.begin(), dp.end());
	int index = p - dp.begin();
	vector<int>res;
	res.push_back(nums[index]);
	for (int i = index; i >= 0; i--)
	{
		if (nums[i] < nums[index] && dp[i] + 1 == dp[index])
		{
			res.insert(res.begin(), nums[i]);
			index = i;
		}
	}
	return res;
}

很明显，上面计算dp数组的时间复杂度是$o(N^2)$,那么这个时间复杂度是不是还可以继续优化一下呢，将时间复杂度优化到$o(NlogN)$，答案是肯定的。

例题8、三角形 LeetCode 120

给定一个二维dp数组，数组以三角形的方式存储，求数字三角形从上到下最小路径和。每次可以向下走相邻的两个位置。

Example:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析：我们定义一个二维 dp 数组，数组的大小和输入数组triangle大小相等，也是一个三角形大小的数组；假设dp[i][j]表示数组三角形到达第i行，第j列的最优解。那么,先以普通思维去做，从上到下寻找最小路径和。
（1）从上到下 up-to-down
边界条件:最坐左边的位置一定只能从正上面下来，则有 $dp[i][0]=triangle[i][0]+dp[i-1][0]$
最右边的位置一定是只能从左上角下来，则有 $dp[i][dp[i].size()-1]=triangle[i][dp[i].size()-1]+dp[i-1][dp[i-1].size()-1]$
状态方程：对于其他位置dp[i][j]，都可以由正上方位置或者左上方位置下来，因此，

$dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]$

完整代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>>dp;
        for(int i=0;i<triangle.size();i++)
            dp.push_back(vector<int>(triangle[i].size(),0));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<dp.size();i++)
        {
            dp[i][0]=dp[i-1][0]+triangle[i][0];
            dp[i][dp[i].size()-1]=dp[i-1][dp[i-1].size()-1]+triangle[i][dp[i].size()-1];
            for(int j=1;j<dp[i].size()-1;j++)
                dp[i][j]=std::min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
        }
        auto p=min_element(dp[dp.size()-1].begin(),dp[dp.size()-1].end());
        return *p;
       
    }
};

（2）从下到上 bottom-to-top
边界条件：dp的最下面一层的值应该等于原始三角形最下面一层的值,有 $dp[dp.size()-1][i]=triangle[dp.size()-1][i]$
状态方程：当前位置只能是从正下方位置或者右下方位置上来，因此有，

$dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]$

完整代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>>dp;
        for(int i=0;i<triangle.size()-1;i++)
            dp.push_back(vector<int>(triangle[i].size(),0));
        dp.push_back(triangle[triangle.size()-1]); //等价于边界条件
      da  for(int i=dp.size()-2;i>=0;i--)
        {
            for(int j=0;j<dp[i].size();j++)
                dp[i][j]=std::min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
        }
        return dp[0][0];
       
    }
};

从上面的两种方法可以看出，倒着来的方式递推会更容易点，而且更少的考虑边界条件问题。其实，这个题我一开始是用一维dp数组去做的，从上到下的方式求路径最小和，每走一次就记住当前位置，一维dp数组空间复杂度更小。可惜，这种方法只通过了21/43，代码如下：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int>dp(triangle.size(),0);
        dp[0]=triangle[0][0];int pos=0;
        for(int i=1;i<triangle.size();i++)
        {  
            dp[i]=dp[i-1]+std::min(triangle[i][pos],triangle[i][pos+1]);
            if(dp[i]==dp[i-1]+triangle[i][pos+1])
                pos=pos+1;
        }
        return dp[triangle.size()-1];
    }
};

例题9、出界的路径 LeetCode 576

有一个m*n大小的网格和一个球，给定球的起始位置(i,j)，球可以每次朝上下左右四个方向移动一个位置。最多可以移动N次。计算球移除边界的路径数，因为可能有太多种可能了，对结果进行一个大数取余，mod=$10^7 +9$。
Example1:

Example2:

分析：同样看到这种关于路径的问题，基本就是动态规划的题目。我们使用一个三维的DP数组，其中dp[k][i][j]表示总共走k步，从(i,j)位置走出边界的总路径数。由于只能上下左右四个方向移动，因此走k步出边界的总路径数一定等于其周围四个位置走k-1步出边界的路径数的总和。
参考代码如下：

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
         vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));
        for (int k = 1; k <= N; ++k) {
            for (int x = 0; x < m; ++x) {
                for (int y = 0; y < n; ++y) {
                    long long v1 = (x == 0) ? 1 : dp[k - 1][x - 1][y];//上
                    long long v2 = (x == m - 1) ? 1 : dp[k - 1][x + 1][y];//下
                    long long v3 = (y == 0) ? 1 : dp[k - 1][x][y - 1];//左
                    long long v4 = (y == n - 1) ? 1 : dp[k - 1][x][y + 1];//右
                    dp[k][x][y] = (v1 + v2 + v3 + v4) % mod;
                }
            }
        } 
        return dp[N][i][j];
    }
};

例题10、棋盘上的骑士 LeetCode 688

给定一个N*N大小的棋盘，骑士的起始位置为(r,c),允许骑士走K步，计算走K步还留在棋盘上的概率。骑士每次可以超8个方向走，类似于中国象棋的马走“日”，如下图示。

Example:
Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

分析：这道题和上面那道题很相似，只不过上面的那道题只能上下左右四个方向移动，而这道题可以朝8个方向移动。在这里，可以使用一个二维矩阵来存储，每一个矩阵中存储方向向量的坐标，即

1	{-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {1, 2}, {2, 1}; // 八个方向

暂时还不会做，这里就不贴代码了。

参考：
https://www.jianshu.com/p/4990e684ac09
https://www.cnblogs.com/grandyang/p/7639153.html

例题11、地下城游戏 LeetCode 174

这道题暂无思路，情况比较复杂，有点难。

最后

不得不说，动态规划的题目都挺难的，有的时候一道题鼓捣一下午，都不见得能做出来，做得都快怀疑人生。

例题7、 最长上升子序列 LeetCode 300

例题8、 三角形 LeetCode 120

例题9、 出界的路径 LeetCode 576

例题10、棋盘上的骑士 LeetCode 688

例题11、地下城游戏 LeetCode 174

最后

例题7、最长上升子序列 LeetCode 300

例题8、三角形 LeetCode 120

例题9、出界的路径 LeetCode 576