坐标型动态规划

1 题型分析

动态规划里较简单一类(以...结尾来分析)
Input是序列或者网格(一维Array，字符串，二维Matrix)
Output是需要找到序列中某个/些子序列或网格中的某条路径
- 某种性质最大/最小
- 计数
- 存在性
动态规划方程dp[i]中的下标i表示以$$a_i$$为结尾的满足条件的子序列的性质；dp[i][j]中的下标表示以格子(i,j）为结尾的满足条件的路径的性质
初始条件dp[0]就是指以$$a_0$$为结尾的子序列的性质

2 序列(Array, String)

序列型dp的状态以i-th为结尾来分析

45. Jump Game II

给一个Array，求从第一个index跳到最后一个index需要的最少步数？

解法1 DP O($$n^2$$)TLE (98/99 pass)

dp[i]表示到达当前点需要的最少步数
从后向前遍历, $$O(n^2)$$
dp[i] = 1 + min(dp[j]) j > i and j can be reached from i by only one jump

解法2 Greedy O(n)

class Solution(object): # 有点难理解
    def jump(self, nums):
        last = cur = res = 0
        for i in xrange(len(nums)): # last 表示最后一步所在位置
            if i > last:
                last = cur
                res += 1
            cur = max(cur, i+nums[i]) # cur 表示当前能达到的最大位置
        return res

53. Maximum Subarray

给一个Array，求和最大的subarray

状态：以i-th个元素为ending的subarray的最大值

Why？只有以最后一个元素结尾，我们才能把结果往后传递，得出递推公式

class Solution(object):
  def maxSubArray(self, nums):
      if not nums: return 0
      cur = res = nums[0]
      for i in xrange(1, len(nums)):
          cur = max(nums[i], cur+nums[i])
          res = max(res, cur)
      return res

Follow up

(1) 空间优化 what if we want to optimize the space complexity?
(2) 返回具体结果 what if we want you to return the start and end indices of the solution array?
- when to move the start and end?
- need sol_start, sol_end

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). 连续子序列Subarray总共也就$$O(n^2)$$个,通过动态规划时间复杂度降为$$O(n)$$,以第i个元素结尾的最长连续子序列可以把递推公式dp[i]和dp[i-1]串起来！

State：dp[i]表示 from the 0-th element to the i-th element, the value of the longest ascending subarray, (including the i-th element)
Init：dp[0] = 1
Function:dp[i] = dp[i-1] + 1(if nums[i] > nums[i-1]) else 1
Answer:dp[n]

3 矩阵(网格)

62 Unique Paths

计数：求总路径数

- **State**: dp[x][y]表示起点到[x,y]路径数
- **Function**: dp[x][y] = dp[x-1][y] + dp[x][y-1]
- **Init**: dp[0][j] = 1, dp[i][0] = 1

63 Unique Paths II

计数：求总路径数，但是有障碍物

64 Minimum Path Sum

最小值：求路径当中最短的路径

361 Bomb Enemy

网格中有wall-'W'，enemy-'E'和empty-'0'，空的地方可以放炸弹，问一个炸弹最多可以炸死多少敌人？有点像游戏“泡泡堂”里的炸弹。

四个方向up,down,left,right

4 空间优化

滚动数组

dp[i] = dp[i-1] + 1
dp[x][y] = dp[x-1][y] + dp[x][y-1]
这种只和前一个或者前一行元素有关的递推公式，可以用滚动数组来做空间优化！
根据行列的大小可以选择更小的来进行滚动，这样更节省空间

1 坐标型动态规划