# Coordinate-based Dynamic Programming

## Introduction

Coordinate-based Dynamic Programming are associated with the coordinates on a array or matrix. You are usually given an array/sequence or a matrix/grid as the input, and the question asks you to find either a subarray, subsequence, vector or path that satisfies a set of conditions. This is one of easier type of Dynamic Programming because it is intuitive to understand.

## Traits

- Usually given an array/sequence or grid/matrix as your input
- Need to find a subsequence/vector/path for
- maximizing/minimizing a certain property
- counting
- true/false

- State Representation:
- State is usually represented by index (i) or (i, j)
- is represented by dp[i] and dp[i][j], which are the most optimal solutions for a[i] or a[i][j]

- Transition:
- Initalization is usually just
`dp[0]`

with`a[0]`

or`a[dp.length-1]`

with`a[a.length-1]`

- At each index i, the most optimal solutions of the surrounding neighbors should be found already
- Update
`dp[i]`

or`dp[i,j]`

with an aggregate function with the values of its neighbors

- Initalization is usually just