Help debug dynamic programming problem!

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Recently, I have encounter this dynamic programming problem and I can not debug where I have problem, I used forward DP style and I have checked the transition and base case. Please help me to look at it, I'm so frustrating. Thank in advance.

Problem link: leetcode

My code:

code

#define ll long long
const ll INF = 1e12;
class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 2, vector<ll>(m + 2, INF));
        for (int j = 1; j <= m - n + 1; j++) {
            dp[1][j] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] != INF) {
                    if (m - j > n - i) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]); // not pick
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(robot[i - 1] - fact[j - 1])); // pick
                }
            }
        }
        return dp[n + 1][m + 1];
    }
};

Updated fix my problem: my for loop only run until i = n, but the final dp state which is dp[n + 1][m + 1] can be reached from dp[n + 1][m] => My for loop should run till n + 1 so this relaxation can happen.

fixed

long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 2, vector<ll>(m + 2, INF));
        for (int j = 1; j <= m - n + 1; j++) {
            dp[1][j] = 0;
        }
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                if (dp[i][j] != INF) {
                    if (m - j > n - i) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
                    if (i - 1 < n && j - 1 < m) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(robot[i - 1] - fact[j - 1]));  
                }
            }
        }
        return dp[n + 1][m + 1];
    }

Comments (2)

Show archived | Write comment?

mohmmdali

19 months ago, hide # |

← Rev. 2 →

Everything looks great to me but the initialization of dp[1][j] = 0, it should be dp[0][j] = 0 and if you are iterating from (m — n +i > j) you should be returning dp[n][m] try these once.

Edited code

#define ll long long
const ll INF = 1e12;
class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 10, vector<ll>(m + 10
        , INF));
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = min(dp[i][j], dp[i][j - 1]);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(robot[i - 1] - fact[j - 1]));
            }
        }
        return dp[n][m];
    }
};

→ Reply

nghia0510

← Rev. 3 →

You should consider all valid costs in all final valid states of $$$i$$$: $$$min_j(dp[n + 1][j])$$$ for all $$$j\in [n + 1, m + 1]$$$ since we have just advertised the cost upwards but yet to finalize any optimal cost at $$$dp[i][m + 1]$$$

lvisbl_'s blog