分治
利用递归可以很快的写出程序
class Solution {
public:
int traverse(vector<vector<int>> &triangle,int x,int y)
{
int n=triangle.size();
if(x==n) return 0;
return triangle[x][y]+min(traverse(triangle,x+1,y),traverse(triangle,x+1,y+1));
}
int minimumTotal(vector<vector<int>> &triangle) {
int ret=traverse(triangle,0,0);
return ret;
}
};
简单是简单，但是由于在计算的过程中，每一个位置都有重复计算，时间复杂度达到了O(2^N);
记忆化搜索
int traverse(vector<vector<int>> &triangle,int x,int y)
{
int n=triangle.size();
if(x==n) return 0;
if(hash[x][y]!=INT_MAX)
{
//如果已经被遍历过
return hash[x][y];
}
hash[x][y]=triangle[x][y]+min(traverse(triangle,x+1,y),traverse(triangle,x+1,y+1));
return hash[x][y];
}
自底而上的动态规划
class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle) {
int n=triangle.size();
vector<int>sum{triangle.back()};
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
sum[j]=triangle[i][j]+min(sum[j],sum[j+1]);
}
}
return sum[0];
}
};
自顶而下的动态规划
自顶而下的动态规划思维更直接，思路更简单
class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle) {
//开数组
if(triangle.size()==0) return 0;
vector<int> f(triangle[triangle.size()-1].size());
//按照一般的想法，应该是开二维数组，但是下一层的f[][]都是来着于上一层的f[][]再加上最短距离
//所以开一维数组就可以完成动态规划，此时f[i]存放的是到第i层的第i个位置的最短距离;
f[0]=triangle[0][0];
//由于数字三角形的最左边和左右边都只有一条路，所以只有一种可能
for(int i=1;i<triangle.size();i++)
{
//倒着遍历，因为需要使用上一层的最短距离的结果，如果是正着遍历
//那么上一层的最短距离还没有被使用就被修改掉
for(int j=triangle[i].size()-1;j>=0;j--)
{
if(j==0)
f[j]=triangle[i][j]+f[j];
else if(j==triangle[i].size()-1)
f[j]=triangle[i][j]+f[j-1];
else
f[j]=min(f[j],f[j-1])+triangle[i][j];
}
}
int ret=INT_MAX;
for(int i=0;i<f.size();i++)
{
ret=min(ret,f[i]);
}
return ret;
}
};
class Solution {
public:
int minPathSum(vector<vector<int>> &grid) {
if(grid.size()==0||grid[0].size()==0)
return 0;
//开数组,
int f[1000][1000];
f[0][0]=grid[0][0];
//第一行和第一列为特殊路径
for(int i=1;i<grid.size();i++)
f[i][0]=grid[i][0]+f[i-1][0];
for(int j=1;j<grid[0].size();j++)
f[0][j]=grid[0][j]+f[0][j-1];
//一般的情况
for(int i=1;i<grid.size();i++)
{
for(int j=1;j<grid[0].size();j++)
{
f[i][j]=grid[i][j]+min(f[i-1][j],f[i][j-1]);
}
}
return f[grid.size()-1][grid[0].size()-1];
}
};
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n));
if(m==0||n==0) return 1;
dp[0][0]=1;
//初始化第一行和第一列
for(int i=1;i<m;i++)
{
dp[i][0]=1;
}
for(int j=1;j<n;j++)
{
dp[0][j]=1;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
class Solution {
public:
bool canJump(vector<int> &a) {
if(a.size()==0)
return true;
vector<bool> dp(a.size());
dp[0]=true;
for(int i=1;i<a.size();i++)
{
for(int j=0;j<i;j++)
{
if(dp[j]&&j+a[j]>=i)
{
dp[i]=true;
break;
}
}
}
return dp[a.size()-1];
}
};
class Solution {
public:
int jump(vector<int> &a) {
vector<int> dp(a.size());
dp[0]=0;
for(int i=1;i<a.size();i++)
{
//假设目前需要的步数很大
dp[i]=INT_MAX;
for(int j=0;j<i;j++)
{
//如果可以从j跳到i
if(j+a[j]>=i)
{
dp[i]=min(dp[i],dp[j]+1);
}
}
}
return dp[a.size()-1];
}
};
这道题属于很经典的动态规划题，也是面试中的高频题目
算法思路
- 因为所求为子序列，很容易想到一种线性动态规划。
- 对于求最长上升子序列，上升我们肯定需要知道当前阶段最后一个元素为多少，最长我们还要知道当前我们的序列有多长。
- 那么我们就可以这样定义状态：设
dp[i]表示以nums[i]为结尾的最长上升子序列的长度，为了保证元素单调递增肯定只能从i前面且末尾元素比nums[i]小的状态转移过来代码思路
状态转移方程为
dp[i]=max0≤j<i,nums[j]<nums[i]dp[j]+1dp[i]=max0≤j<i,nums[j]<nums[i]dp[j]+1
每个位置初始值为
dp[i]=1（将自己作为一个序列）答案可以是任何阶段中只要长度最长的那一个，所以我们边转移边统计答案
class Solution {
public:
int longestIncreasingSubsequence(vector<int> &nums) {
if(nums.size()==0) return 0;
//设置初始的最大值
int ret=1;
vector<int> dp(nums.size());
for(int i=0;i<nums.size();i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
//如果以nums[j]的值小于nums[i],更新dp[i];
if(nums[j]<nums[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
}
//更新最长子序列的最大值
ret=max(ret,dp[i]);
}
return ret;
}
};
除了上面的一般动态规划，还可以使用二分对其进行优化
算法思路
- 设
dp[i]表示长度为i的最长上升子序列的末尾元素的最小值，显然这个数组的权值一定单调不降。- 于是我们按顺序枚举数组
nums，每一次对dp数组二分查找，找到小于nums[i]的最大的dp[j]，并更新dp[j+1]。
class Solution {
public:
int longestIncreasingSubsequence(vector<int> &nums)
{
if (nums.size() == 0)
{
return 0;
}
int dp[nums.size() + 1];
int ans = 1;
dp[0] = 0;
dp[1] = nums[0];
for (int i = 1; i < nums.size(); i++) {
// nums[i]比最长的末尾元素的都大，直接更新
if (nums[i] > dp[ans])
{
ans++;
dp[ans] = nums[i];
}
else
{ // 二分查找nums[i]可以放到dp数组的哪个数后面
int left = 1;
int right = ans;
while (left < right)
{
int mid = (left + right) / 2;
if (nums[i] <= dp[mid])
{
right = mid;
}
else
{
left = mid + 1;
}
}
int j = left - 1;
dp[j + 1] = min(nums[i], dp[j + 1]);
}
}
return ans;
}
};