# 2D DP

When considering DP problems in dimensions, we can summary DP problems as 1D DP, 2D DP and 3D DP.

For 1D DP, the most classical one Fibonacci numbers. Also, we have the stair climbing problem.

For 2D DP, the most classical one is 0–1 knapsack problems.

From my previous post here, there is a very interesting examples to compare two examples: one is 1D DP one can be solved by 2D DP. And the later one is essential a 0–1 knapsack problems.

I will put more 2D DP problems here to help the reader improve your DP skills. Also, I will summarize some 3D DP in another article here:

# 1155. Number of Dice Rolls With Target Sum

//2D space O(nd)const int mod = 1e9 + 7;

void add(int &a, int b){

a +=b;

if(a>=mod)a-=mod;

}

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

vector<vector<int>> ways(d+1, vector<int>(target+1));

ways[0][0] = 1; //empty will have sum of 0

for(int roll =1;roll<=d;++roll){

//vector<int> new_ways(target+1);

for (int sum=0;sum<=target;++sum){

for (int this_roll=1;this_roll<=f;++this_roll){

int new_sum = sum+this_roll;

if (new_sum<=target){

ways[roll][new_sum] += ways[roll-1][sum];

//new_ways[new_sum] += ways[sum];

if(ways[roll][new_sum] >=mod)ways[roll][new_sum] -=mod;

}

}

}

//ways = new_ways;

}

return ways[d][target];

}

};

Improve to use 1 D space

`//1d space push forward`

const int mod = 1e9 + 7;

void add(int &a, int b){

a +=b;

if(a>=mod)a-=mod;

}

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

vector<int> ways(target+1);

ways[0] = 1; //empty will have sum of 0

for(int roll =1;roll<=d;++roll){

vector<int> new_ways(target+1);

for (int sum=0;sum<=target;++sum){

for (int this_roll=1;this_roll<=f;++this_roll){

int new_sum = sum+this_roll;

if (new_sum<=target){

new_ways[new_sum] += ways[sum];

if(new_ways[new_sum]>=mod)new_ways[new_sum]-=mod;

}

}

}

ways = new_ways;

}

return ways[target];

}

};

1D Space look backwards

`//1d space look backward`

const int mod = 1e9 + 7;

void add(int &a, int b){

a +=b;

if(a>=mod)a-=mod;

}

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

vector<int> ways(target+1);

ways[0] = 1; //empty will have sum of 0

for(int roll =1;roll<=d;++roll){

vector<int> new_ways(target+1);

for (int sum=0;sum<=target;++sum){

for (int this_roll=1;this_roll<=f;++this_roll){

int back_sum = sum-this_roll;

if (back_sum>=0){

new_ways[sum] += ways[back_sum];

if(new_ways[sum]>=mod)new_ways[sum]-=mod;

}

}

}

ways = new_ways;

}

return ways[target];

}

};

Prefix sum

`//1d space look backward`

const int mod = 1e9 + 7;

void add(int &a, int b){

a +=b;

if(a>=mod)a-=mod;

}

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

vector<int> ways(target+1);

ways[0] = 1; //empty will have sum of 0

for(int roll =1;roll<=d;++roll){

for(int i=1;i<=target;++i)add(ways[i], ways[i-1]);

vector<int> new_ways(target+1);

for (int sum=1;sum<=target;++sum){

new_ways[sum] = ways[sum-1]-(sum-1-f>=0?ways[sum-1-f]:0);

if(new_ways[sum]<0)new_ways[sum]+=mod;

/*

for (int this_roll=1;this_roll<=f;++this_roll){

int back_sum = sum-this_roll;

if (back_sum>=0){

new_ways[sum] += ways[back_sum];

if(new_ways[sum]>=mod)new_ways[sum]-=mod;

}

}

*/

}

ways = new_ways;

}

return ways[target];

}

};

A naive solution will get TLE.

For this naive solution, we consider about all the possible locations to put a mailbox.

`dp(x, M) means is the cost of all houses at the left part of location x when we are using M mailbox. If the location x is fixed, then the left part houses's cost are fixed.`

However, the above idea based code got TLE. The reason might be, the complexity of this algorithm is O(KKT) where K is the maximum house location, T is the number of mailboxes.

# Unoptimized solution got TLE

# States: x is the last mailbox location looking from left to right

# M: is used mailboxes

# mailbox can be put anywhere.class Solution:

def minDistance(self, houses: List[int], T: int) -> int:

houses.sort()

N = len(houses)

if T==1:

return min( sum(abs(houses[j]-houses[i]) for j in range(N))

for i in range(N))

from functools import lru_cache

@lru_cache(None)

def dp(x, M):

if x<houses[0]:

return float('inf')

if x<M:return float('inf')

if M==1:

jjjj=bisect.bisect(houses, x)

if jjjj==0:return float('inf')

return sum(x-houses[jjj] for jjj in range(jjjj))

i = bisect.bisect_right(houses, x)

this_res = float('inf')

for last in range(x):

jj = bisect.bisect_right(houses, last)

cand = list(range(jj, i))

if not cand:delta=0

else:

delta = sum(min(abs(houses[j]-last), abs(houses[j]-x)) for j in cand)

this_res = min(this_res, dp(last, M-1)+delta)

return this_res

ret = float('inf')

ret = min(dp(houses[-1], T), ret)

for last in range(1, houses[-1]):

kkk = bisect.bisect(houses, last)

cand = list(range(kkk, N))

if not cand:delta=0

else:

delta = sum(houses[-1]-last for j in cand)

ret = min(dp(last, T)+delta, ret)

return ret

A better way can be found:

C++ : this is cui aoxiang’s live coding.

The critical part is figuring out “**Why does the median minimize the sum of absolute deviations?**”

We can find a nice explanation from THIS LINK.

“Imagine the given values as trees along a road. The quantity you are trying to minimize is the sum of distances between you and each of the trees.

Suppose that you are standing at the median, and you know the current value of the sum. How will it change if you move in either direction? Note that regardless of which direction you choose, in each moment you will be moving

away fromat least half of the trees, andtowardsat most half of the trees. Therefore, the sum of distances can never decrease — and that means the sum of distances at the beginning had to be optimal.” —

Michal Forišek