2D DP

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];
}
};
//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 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];
}
};
//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];
}
};
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.
# 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi