Leetcode题目总结3-动态规划

本文根据处理对象的结构将动态规划分为线性一维、矩形二维、三角形这三种类型。

1. 算法讲解

1.1 简介

动态规划脱胎于暴力解法，通过优化重叠子问题形成了DP这种高效的解法。

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。分治法也是将问题分为若干个子问题，但经分解后得到的子问题往往不是互相独立的。

要解决动态规划(dp)的问题需要考虑四个步骤：

1. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来
2. 状态转移方程和转移条件：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
3. 初始状态的本质是递推，递推就需要明确初始条件。
4. 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件

其实最主要的还是考虑23，转移方程转移条件和初始状态！

以爬楼梯为例，假设每次爬楼梯只能爬1步或2步，求爬到第n阶有多少种办法？

• 确定状态和状态变量：爬到第i层所需要的步数dp。

• 转移方程：dp[i] = dp[i - 1] + dp[i - 2]。

• 初始条件：dp[0] = 1;和dp[1] = 2;

• 边界条件：第n层结束。

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

1.2 解法

前面说到，动态规划脱胎于暴力解法，需要优化。优化的办法有两种：带备忘录的递归解法（自顶向下），动态规划解法（自底向上）

带备忘录的递归优化

一个斐波那契数列的暴力解法如下，画出递归树后发现了大量重复的子问题，因此导致时间复杂度很高（呈指数上升$O(2^n)$）

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

因此我们想到利用一个备忘录记载用过的子问题：

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != 0) return memo[n];
    // 未被计算过
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

由于递归的时候，先从左子树一路向下，因此通过备忘录就能实现剪枝：

如上图所示，直接把$2^n$的树形结构，剪成了nn的一维数组结构，大大减小了时间复杂度！

动态规划优化

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一个专门的容器，直接在这个容器中完成所有算法，这样时间和备忘录一样，但空间更节省。这就是自底向上。

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

2. 线性一维DP

005 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

解答：

这里的一维是指处理对象的维度，dp容器可以是二维的。解答思路很简单，如果abba是回文，则bb肯定是回文。

一定要写l <= length，因为这里的l代表了回文的长度，如果aaaa则l==length。

这道题要维护两个重要变量，回文串起始位置start和长度len

string longestPalindrome(string s) {
    const int length = s.size();
    //最后返回字符串，返回的记录方式是：位置(start)+长度（maxlen）
    int maxlength = 1, start = 0;
    if (length == 0) return s;
    vector<vector<bool>> dp(length + 1, vector<bool>(length + 1, false));

    for (int i = 0; i < length; i++) //这里一定不能写length-1
    {
        //初始化
        dp[i][i] = true;
        if (i < length - 1 && s.at(i) == s.at(i + 1))//必须在这里判断
        {
            dp[i][i + 1] = true;
            start = i;
            maxlength = 2;
        }
    }

    //一定要写等于
    for (int l = 3; l <= length; l++)
        for (int i = 0; i <= length - l; i++) //这里也一定要加等号
        {
            int s_start = i;
            int s_end = i + l - 1;
            if (dp[s_start + 1][s_end - 1] && s.at(s_start) == s.at(s_end))
            {
                dp[s_start][s_end] = true;
                maxlength = l;
                start = s_start;
            }
        }
    if (maxlength >= 2) return s.substr(start, maxlength);
    //maxlength=1时，直接返回第一个字符（要写成串的形式）
    else return s.substr(0, 1);
}

053 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解答：

最重要是写出转移方程sum[i]=max(sum[i-1]+a[i],a[i]);只要a[i]不是大，当前组就还有机会靠下一个a[i+1]翻盘。

std::max_element()返回的是迭代器位置，所以还需要解引用。

int maxSubArray(vector<int>& nums) {
    if(nums.size()==0) return 0;
    vector<int> sum(nums.size());
    sum[0]=nums[0];
    for(int i=1;i<nums.size();i++)
        sum[i]=max(sum[i-1]+nums[i],nums[i]);
    return *max_element(sum.begin(), sum.end());
}

055 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解答：

贪心算法，计算每个点能跳跃到的最大长度

bool canJump(vector<int>& nums) {
    int canReach=0;
    for(int i=0;i<nums.size();i++){
        if(i>canReach){
            return false;
        }
        canReach=max(canReach,nums[i]+i);
    }
    return true;
}

091 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)

解答：

这道题引入了转移条件：

• 只要前一位不为0，就可以dp[i]+=dp[i-1]
• 只要前两位组合在[10,26]之间，就可以dp[i]+=dp[i-2]

要注意dp[m]不是表示s的下标，而是表示长度，表示第m位！dp[0]=dp[1]=1，dp[0]表示第0位（这是虚拟状态，有利于做题而已），dp[1]表示第1位。

凡是涉及到要索引上上位，都可以考虑使用虚拟状态。

int numDecodings(string s) {
    if(s.empty()) return 0;
    if(s[0]=='0') return 0;
    vector<int> dp(s.size()+1,0);
    dp[0]= 1;
    dp[1]= 1;
    for(int i=2;i<s.size()+1;i++)
    {
        if(s[i-1]!='0') dp[i]+=dp[i-1];
        if(s.substr(i-2,2)>="10"&&s.substr(i-2,2)<"27") 
            dp[i]+=dp[i-2];
    }
    return dp[s.size()];
}

096 不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树

解答：

这个题必须要考虑0个节点时，依然是一个二叉搜索树NULL。状态转移方程：dp[i] += dp[left] * dp[right]。dp[num]代表了num个节点能够组成多少个BST。

int numTrees(int n) {
    vector<int> dp(n+1);
    dp[0]=dp[1]=1;
    if(n==0||n==1) return 1;
    for(int num=2;num<=n;num++)//有多少个节点
        for(int left=0;left<num;left++)
        {
            int right = num-left-1;//要分配一个为root
            dp[num]+=dp[left]*dp[right];
        }
    return dp[n];
}

121 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

解答：

维护两个变量minPrice[i]和maxProfit[i]

int maxProfit(vector<int>& prices) {
    vector<int> minprice(prices.size());
    vector<int> maxprofit(prices.size());
    if(prices.size()==0) return 0;
    minprice[0]=prices[0];
    maxprofit[0]=0;
    for(int i=1;i<prices.size();i++)
    {
        minprice[i]=min(prices[i],minprice[i-1]);
        int curprofit = prices[i]-minprice[i];
        maxprofit[i]=max(curprofit,maxprofit[i-1]);
    }
    return maxprofit[prices.size()-1];
}

122 买卖股票的最佳时机II

比上一道题目加了条件：多次买卖一支股票

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解答：

因为同一天又能买又能卖，所以转移方程dp[i]=max(dp[i-1]+p[i]-p[i - 1],dp[i-1])

int maxProfit(vector<int>& prices) {
    if(prices.size()==0) return 0;
    vector<int> maxProfit(prices.size(),0);
    for(int i=1;i<prices.size();i++)
        maxProfit[i]=max(maxProfit[i-1],maxProfit[i-1]+prices[i]-prices[i-1]);
    return maxProfit[prices.size()-1];
}

152 乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

解答：

由于乘法的特殊性，两个转移变量，同时需要比较三个变量的最大最小。注意一下maxvec不是递增序列，需要返回一个最大值。

int maxProduct(vector<int>& nums) {
    if(nums.size()==0) return 0;
    if(nums.size()==1) return nums[0];
    vector<int> maxvec(nums.size());
    vector<int> minvec(nums.size());
    maxvec[0]=minvec[0]=nums[0];
    for(int i=1;i<nums.size();i++)
    {
        maxvec[i]=max3(maxvec[i-1]*nums[i],nums[i],minvec[i-1]*nums[i]);
        minvec[i]=min3(minvec[i-1]*nums[i],nums[i],maxvec[i-1]*nums[i]);
    }
    return *max_element(maxvec.begin(),maxvec.end());
}
int max3(int a, int b, int c)
{
    return max(a,max(b,c));
}
int min3(int a, int b, int c)
{
    return min(a,min(b,c));
}

198 打家劫舍

如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4

解答：

转移方程很简单dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);，需要注意一下初始条件。

int rob(vector<int>& nums) {
    int len = nums.size();
    if(len==0) return 0;
    if(len==1) return nums[0];
    vector<int> dp(len);
    dp[0]=nums[0];
    dp[1]=max(nums[0],nums[1]);
    for(int i=2;i<len;i++)
    {
        dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    }
    return dp[len-1];
}

213 打家劫舍II

这个地方所有的房屋都围成一圈

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

解答：

分类讨论，每次讨论时，前3个初始变量都需要考虑

int rob(vector<int>& nums) {
    int n=nums.size();
    if(n==0) return 0;
    vector<int> dp1(nums.size());
    vector<int> dp2(nums.size());
    if(n<=3) return *max_element(nums.begin(),nums.end());
    //偷第一家
    dp1[0]=dp1[1]=nums[0];
    dp1[2]=nums[0]+nums[2];
    for(int i=3;i<n-1;i++)
        dp1[i]=max(dp1[i-2]+nums[i],dp1[i-1]);
    //不偷第一家
    dp2[0]=0;
    dp2[1]=nums[1];
    dp2[2]=max(nums[1],nums[2]);
    for(int i=3;i<n;i++)
        dp2[i]=max(dp2[i-2]+nums[i],dp2[i-1]);
    return max(*max_element(dp1.begin(),dp1.end()),
               *max_element(dp2.begin(),dp2.end()));
}

3. 矩形二维DP

062 不同的路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

解答：

转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]，注意边界的转移条件。

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

063 不同路径II

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

解答：

需要分类讨论。由于加了障碍物所以需要特别考虑边的情况，看看是否有东西堵住。需要注意：初始化要放到循环里面。

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

064 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解答：

需要分类讨论。dp[i][j]+=dp[i][j-1];不是这样的，和前面区分好！

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

221 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

输入: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

解答：

和前面的路径题非常相似，但需要比较3个中的最小者。

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty())
        return 0;
    int M = matrix.size();
    int N = matrix[0].size();
    vector<vector<int>> dp(M, vector<int>(N, 0));
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
        {
            if(matrix[i][j]!='1') continue;
            if(i==0||j==0) dp[i][j]=1;
            else dp[i][j]=min(dp[i-1][j-1],
                          min(dp[i-1][j],dp[i][j-1]))+1;
        }
    int res=0;
    for(auto x:dp)
        res=max(res,*max_element(x.begin(),x.end()));
    return res*res;
}

4. 三角形二维DP

118 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解答：

两边要特别处理。每次需要resize一下，因为维度都不相同。

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> dp(numRows);
    if(numRows==0)
        return dp;
    for(int i=0;i<numRows;i++)
    {
        dp[i].resize(i+1); //对dp[i]resize而不是dp
        dp[i][0]=dp[i][i]=1;
        for(int j=1;j<i;j++) //i=0被直接跳过
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
    }
    return dp;
}

119 杨辉三角II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

输入: 3
输出: [1,3,3,1]

解答：

如果按照上一题的思路老实推的话，占用空间较大。这里选择原地修改的办法。

vector<int> getRow(int rowIndex) {
    vector<int> dp(rowIndex +1);
    if (rowIndex == 0)
        return dp;
    //i代表第几行
    for (int i = 0; i < rowIndex; i++)
    {
        dp.resize(i + 1);
        dp[0] = dp[i] = 1;
        //原地修改
        for (int j = 1; j < i; j++)
            dp[j] = dp[j] + dp[j - 1];
    }
    return dp;
}

120 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

解答：

和前面的三角并没有什么不用，还是要注意两边，另外初始化的resize要特别注意。

int minimumTotal(vector<vector<int>>& triangle) {
    int rowSize = triangle.size();
    if (rowSize == 0) return 0;
    int colSize = triangle[0].size();
    vector<vector<int>> dp(rowSize);
    dp[0].resize(1);//没有这一句内存会出错
    dp[0][0] = triangle[0][0];
    for (int i = 1; i < rowSize; i++)
    {
        dp[i].resize(i + 1);
        dp[i][0] = dp[i - 1][0] + triangle[i][0];
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        for (int j = 1; j < i; j++)
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
    }
    return *min_element(dp[rowSize - 1].begin(), dp[rowSize - 1].end());
}