LeetCode——动态规划问题(简单难度)

By AverageJoeWang
 标签:

动态规划概述

动态规划(英语:Dynamic programming,简称DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。

解题步骤

解决动态规划类问题,分为两步:

  • 1.确定状态
  • 2.根据状态列状态转移方程

经典例题

303.区域和检索 - 数组不可变

  • 解题思路
    • 每一步都是前一步之和,nums的vector用来存储原来每一个索引的内容,dp是vector用来存储前k次的结果,比如dp[4]就是存储[0,4]的结果
    • dp[i] = nums[i] + dp[i-1]
  • 代码
class NumArray {
public:


    NumArray(vector<int> nums) {
        arr = nums;
        for(int i = 0; i < arr.size(); i++){
            arr[i] += arr[i-1];
        }
    }

    int sumRange(int i, int j) {
        return i == 0 ? arr[j] : arr[j] - arr[i - 1];
    }

private:
    vector<int> arr;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

121. 买卖股票的最佳时机

  • 转移方程:maxSum = dp[max] - dp[min],max > min

  • 代码

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

70. 爬楼梯

  • 转移方程dp[i] = dp[i-1] + dp[i-2],i > 2
  • 代码
class Solution {
public:
    int climbStairs(int n) {
        if(n == 0)
            return 0;
        else if(n == 1) 
            return 1;
        else if(n == 2) 
            return 2;
        else{
            int a[n];
            a[0] = 1;
            a[1] = 2;
            for(int i = 2; i < n ;i++)
            {
                a[i] = a[i - 1] + a[i - 2];
            }
            return a[n-1];
        }

    }
};

198. 打家劫舍

  • 转移方程:dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]),i s> 2,dp是用来存储每一步最好的结果,nums是每一个索引的值

  • 代码

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

746. 使用最小花费爬楼梯

  • 转移方程: dp[i] = min(dp[i-2]+cost[i-2], dp[i-1] + cost[i-1]),cost是每一步的花费,dp是存储每一步最好的结果
  • 代码
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size() == 2) return min(cost[0], cost[1]);
        vector<int> dp(cost.size(), 0);
        for(int i = 2; i < cost.size() + 1; i++){
            dp[i] = min(dp[i-2]+cost[i-2], dp[i-1] + cost[i-1]);
        }
        return dp[cost.size()];
    }
};

53. 最大子序和

  • 转移方程:maxSum = max(maxSum,max(nums[i], sum + nums[i]))
  • 代码
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.size(); i++){
            sum = max(nums[i], sum + nums[i]);
            if(maxSum < sum) maxSum = sum;
        }
        return maxSum;
    }
};

总结

解决动态规划类问题,分为两步:1.确定状态,2.根据状态列状态转移方程