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