坐标型动态规划

• states
• f[x]表示我从起点走到坐标x......
• f[x][y]表示我从起点走到坐标x,y......
• function:研究走到x,y这个点之前的一步• initialize:起点

• answer:终点

• Triangle

• Pascal's Triangle

• Pascal's Triangle II
• Minimum Path Sum
• unique path
• unique path ii

Triangle

top-down and bottom-up are the same

Pascal's Triangle

要得到一个帕斯卡三角，我们只需要找到规律即可。

• 第k层有k个元素
• 每层第一个以及最后一个元素值为1
• 对于元素A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n]

Pascal's Triangle II

数组滚动计算 + 倒叙计算

[ rows = 5
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

不同于上一题，这里我们仅仅需要得到的第k层的集合，但只能使用O(k)的空间。所以不能用前面二维数组的方式，只能使用一位数组滚动计算。

在第一题里面，我们知道，帕斯卡三角的计算公式是这样的，A[k][n] = A[k-1][n-1] + A[k-1][n]。

假设现在数组存放的第3层的数据，[1, 3, 3, 1]，如果我们需要计算第4层的数据，如果我们从前往后计算，譬如A[4][2]= A[3][1] + A[3][2]，也就是4，但是因为只有一个数组，所以需要将4这个值覆盖到2这个位置，那么我们计算A[4][3]的时候就会出现问题了，因为这时候A[3][2]不是3，而是4了。

为了解决这个问题，我们只能从后往前计算，仍然是上面那个例子，我们实现计算A[4][3] = A[3][2] + A[3][3]，也就是6，我们将6直接覆盖到3这个位置，但不会影响我们计算A[4][2]，因为A[4][2] = A[3][1] + A[3][2]，已经不会涉及到3这个位置了。

Minimum Path Sum

state: f[x][y]从起点走到x,y的最短路径

function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]

initialize: f[i][0] = sum(0,0 ~ i,0);

            f\[0\]\[i\] = sum\(0,0 ~ 0,i\)

answer: f[n-1][m-1]