lettcode 动态规划 easy

• House Robber
  一个数组中找出子数组和最大的和，要求数组中的数字不能连续出现。例如 [1, 2, 3, 1] 和最大为 4 ，是 1 和 3 的和；[2, 7, 9, 3, 1]，和为 12，是 2，9，1 的和。

def rob1(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    a,b=0,0
    for i in range(len(nums)):
        if i%2==0:
            a=max(a+nums[i],b)
        else:
            b=max(b+nums[i],a)
    return max(a,b)

• Paint House
  染房子，只有三种颜色，相邻房子不能同色，求最小花费。
  思路来源于网络
  思路: 每个房子有三种方案, 那么如果当前房子染一个色的话, 最小代价将是上一个房子的另两种颜色的最小代价+当前房子染色的代价。所以

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1];
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2];

# 代码来源于网络
class Solution {  
public:  
    int minCost(vector<vector<int>>& costs) {  
        if(costs.size()==0) return 0;  
        int len = costs.size();  
        vector<vector<int>> dp(len+1, vector<int>(3, 0));  
        for(int i = 1; i <= len; i++)  
        {  
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];  
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1];  
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2];  
        }  
        return min(dp[len][0], min(dp[len][1], dp[len][2]));  
    }  
}; 

• Paint Fence
  涂栅栏，n 个栅栏 k 种颜色
  任意两个栅栏不能同色

def numWays(n, k):
    dp = [0, k, k*k, 0]
    if n <= 2 :
        return dp[n]
    for i in range(2, n):
        dp[3] = (k-1) * (dp[1] + dp[2])
        dp[1] = dp[2]
        dp[2] = dp[3]
    return dp[3]

• Range Sum Query - Immutable
  求取一个数组区间的和
  题目给出很明确的要求， 对这个函数会有很多次调用，数组不会改变
  思路：如果是直接求取区间内的和，那么肯定会超时。换一个思路，如果能知道 i -1 位置之前的和，j 位置之前的和，那么 i 到 j 位置的和就显而易见了。j 位置的和 - i-1 位置的和即可。
  例如 [-2, 0, 3, -5, 2, -1]，求取2，5 之间的和。
  那么知道 2-1=1 位置的和为 -2，5位置的和为 -3
  那么 2 - 5 之间的和为 -3 - (-2) = -1。注意 2 和 5 是数组的下标。

class NumArray(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        # 这是一个数组，保存到当前位置的和
        self.dp = nums
        for i in xrange(1, len(nums)):
            self.dp[i] += self.dp[i-1]
        
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.dp[j] - (self.dp[i-1] if i > 0 else 0)

• Best Time to Buy and Sell Stock
  数组内是一个物品的价格变化情况，问在什么情况下能够获得最大利润，即最高价 - 最低价

Input: [7,1,5,3,6,4]
Output: 5
# 在 1 的时候购入，在 6 的时候卖出。得到最大利润 5

def maxProfit(prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length < 2:
            return 0
        min = prices[0]
        maxdiff = prices[1] - min
        for i in range(2,length):
            if prices[i-1] < min:
                min = prices[i-1]
            curdiff = prices[i] - min
            maxdiff = max(maxdiff, curdiff)
        if maxdiff <= 0:
            return 0
        return maxdiff

• Maximum Subarray

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

如果当前和为负数，那么根本没有加的必要，直接从当前位置开始累加即可，然后与当前的最大值进行比较即可。

def maxSubArray(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return
        cur_sum = 0
        max_sum = nums[0]
        for i in nums:
            if cur_sum < 0:
                cur_sum = i
            else:
                cur_sum += i
            #if cur_sum > max_sum:
                #max_sum = cur_sum
            max_sum = max(cur_sum, max_sum)
        return max_sum

• Climbing Stairs
  爬楼梯，一次可以爬一个台阶，也可以爬两个台阶，对于一个有 n 个台阶的楼梯，有对少种爬法？

def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 1
        dp = [i for i in range(n)]
        dp[0], dp[1] = 1, 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

• Min Cost Climbing Stairs
  数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。
  每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

Input: cost = [10, 15, 20]
Output: 15
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

注意，最终目的是跳上这个楼梯，意味着最后一个楼梯也要计算在内。
思路：当前楼梯的最小花费取决于前两个楼梯的花费，意味着第 i 层楼梯的花费是当前花费 + min(第 i-1 层楼梯的花费，第 i-2 层楼梯的花费)，得到递推关系式就比较好解决了。

def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        n = len(cost)
        if n == 0:
            return 0
        dp = [0 for _ in range(n)]
        dp[0], dp[1] = cost[0], cost[1]
        
        for i in range(2, n):
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        return min(dp[-1], dp[-2])
# O(1) 空间
def test(cost):
    dp0, dp1, dp2 = 0, 0, 0
    for i in range(2, len(cost) + 1):
        dp2 = min(dp0 + cost[i - 2], dp1 + cost[i - 1])
        dp0,dp1 = dp1,dp2
    return dp2