# 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 = 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 forwardconst 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 = 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 backwardconst 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 = 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 backwardconst 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 = 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:                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`

--

--