leetcode之动态规划 easy部分

发表于

记录自己在学习算法过程中遇到的动态规划的题目，easy部分。

1025 Divisor Game

题目描述

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player’s turn, that player makes a move consisting of:

Choosing any x with 0 < x < N and N % x == 0.
Replacing the number N on the chalkboard with N - x.
Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

题目解析

给定N，Alice和Bob轮流选择能被N整除的数字x（0 < x < N）,N = N - x，直至某一方找不出数字为止。若Alice赢，返回True，否则返回false。
设res为游戏结果，程序返回的是res[N]。
res[0] = false;
res[1] = false;
设Alice给出的数字为i，需要找到一个j，使得i % j == 0，且res[i-j] = false，此时res[i] = true，也就是Alice赢了。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool divisorGame(int N){
        vector<bool> res(N+1,false);
        res[0] = false;
        res[1] = false;
        for(int i=2;i<=N;i++)
            for(int j=1;j<i;j++)
                if(i % j == 0)
                    if(res[i-j] == false){
                        res[i] = true;
                        break;
                    }
        return res[N];
    }
};

另外一种思路就是判断N是否为偶数。站在Alice的角度，对于N来说，主要有以下情况：
如果N是偶数，Alice坚持选择x = 1，那么Bob得到的是N-x是奇数，Bob有两种情况：
Bob得到的是1，无法给出选择，Bob输，Alice赢。
Bob得到的N是大于1的奇数，奇数的因子x仍然是奇数，N-x为大于1的偶数，Alice总可以给出选择。
因此当N是偶数时，只要坚持x=1，轮到Alice时总能得到一个大于1的偶数，直至Bob得到的数字为1，Bob输。

1
2
3
4
5
6
class Solution {
public:
bool divisorGame(int N){
    return (N%2 == 0);
    }
};

参考

https://massivealgorithms.blogspot.com/2019/04/leetcode-1025-divisor-game.html
https://xingxingpark.com/Leetcode-1025-Divisor-Game/

303 Range Sum Query - Immutable

八百年没坐汽车，早上6点起来赶车，汽车居然还坏了，现在滞留在火车站，等5个小时，找了一个咖啡厅，在火车站登录不上英文的官网了，无奈只能注册了中文社区的账号，之前没怎么做过动态规划的题目，一时不是很适应动态规划的思想。

题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

1
2
3
4
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

题目解析

给定一个数组，可以假定它是不变的，给定一个i和j，求下标i到j的数组元素之和，包含边界的元素。题目中提示了会多次调用sumRange函数，如果每次都是根据给定的下标遍历数组，事件复杂度会比较高，要使用动态规划的思想，在计算过程中存储每次调用sumRange函数求解子问题的计算结果。具体思路是申请一个数组dp来进行累加前j项的和，如果i不为0，则结果是dp[j]-dp[i-1]，如果i为0，则结果是dp[j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
public:
    vector<int> dp;
    NumArray(vector<int>& nums) {
        dp = nums;
        for(int i=1;i<nums.size();i++)
            dp[i] += dp[i-1];
        
    }
    
    int sumRange(int i, int j) {
        if(i == 0)
            return dp[j];
        else
            return dp[j] - dp[i-1];       
    }
};

参考

https://www.cnblogs.com/grandyang/p/4952464.html

121 Best Time to Buy and Sell Stock

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

题目解析

题目给定一个数组，表示股票每天的交易价格，在这样的价格趋势下，如果只完成一笔交易，求解利润的最大值。卖出价格要高于买入的价格，不能在买入之前卖出。最大利润在当前卖出价格一定的情况下，买入价格越低，利润越大。遍历数组，维护一个在第i天之前的最低价格变量和一个第i天时的最大利润变量，当一次遍历完成后，就得到了最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:

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

53

题目描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

题目解析

题目给定一个整数数组，找出一个具有最大和的连续子数组。使用动态规划的思想，dp[i]表示在前i个元素中最大和的值。那么dp[i]有两种情况，要么是只有nums[i]元素自己，dp[i] = nums[i]；要么是前i-1个元素中的最大和与nums[i]的和，遍历nums数组，比较nums[i]与dp[i-1]+nums[i]的最大值。这样就求取了dp[0]、dp[1]、dp[2]….dp[nums.size()-1]。dp数组中的最大值就是题目要求的连续子数组中的最大和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        int res = dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            if(res < dp[i])
                res = dp[i];
        }
        return res;     
    }
};

参考

https://www.cnblogs.com/patatoforsyj/p/9463945.html

392

题目描述

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

1
2
3
4
5
6
7
Example 1:
s = "abc", t = "ahbgdc"
Return true.

Example 2:
s = "axc", t = "ahbgdc"
Return false.

题目解析

判断字符串s是否为t的子序列，子序列可以要求不连续，只要保持字符串中字符的相对顺序就可以。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int index = -1;
        for(int i=0;i < s.length();i++){
            index = t.find(s[i],index+1);
            if(index == string::npos)
                return false;
        }
        return true;   
    }
};

70

题目描述

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

题目解析

爬n阶楼梯，一次可以爬1或2个台阶，求解一共有多少种方法爬到楼顶。设dp[i]是爬i阶楼梯的方法之和，那么dp[0] = 0,dp[1] = 1,dp[2] = 2,dp[i] = dp[i-1] + dp[i-2]，对于第i(i>2)阶,可以在第i-1阶再爬一个台阶，或者是在第i-2阶爬2个台阶。我的解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int climbStairs(int n) {
        if(n > 2){
            vector<int> dp(n+1,0);
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            for(int i=3;i<=n;i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
        else
            return n;   
    }
};

746 Min Cost Climbing Stairs

题目描述

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

1
2
3
4
5
6
7
8
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

题目解析

开始分不清这个数组下标，题目描述说每当爬上一个台阶都要花费对应的cost[i]，然后还可以上1个或2个台阶。开始可以从0或1开始，那dp[0] = 0,dp[1] = 0,dp[i]有两种情况，一种是爬到第i-1，然后上1层台阶，此时的花费是cost[i-1]+dp[i-1]，或者是爬到第i-2层，然后上2层台阶，此时的花费是cost[i-2]+dp[i-2]，然后取两者中的最小值。注意此时的dp[i]表示爬上i层台阶花费的体力值，不包括cost[i]。那么求解的结果就是dp[cost.size()]。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1,0);
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2;i<=cost.size();i++){
            dp[i] = min(cost[i-2] + dp[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[cost.size()];   
    }
};

198 House Robber

题目描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

题目解析

这道题目和爬台阶的题目类似，小偷偷盗的房屋两间不能连着，求偷盗的最高金额。对于第i间房屋来说，dp[i] = max(dp[i-2]+nums[i],dp[i-1],dp[0] = nums[0]，dp[1] = max(nums[1],nums[0])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        vector<int> dp(n,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        int res = dp[1];
        for(int i=2;i<n;i++){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
            //cout << dp[i] << endl;
            if(res < dp[i])
                res = dp[i];    
        }
        return res;
    }
};