LintCode "Minimum Adjustment Cost"

2D DP. DP is all about choices - current choice with previous choice :) A natural solution as below, and of course we can simply use rolling array for better memory utilization.

class Solution {
    const int MaxNum = 101;
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target)
    {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int>(MaxNum, INT_MAX));

        for(int i = 0; i < MaxNum; i ++)
            dp[0][i] =  abs(i - A[0]);

        for(int i = 1; i < n; i ++)
        {
            for(int k = 0; k < MaxNum; k ++)
            {
                int cost = abs(k - A[i]);
                for(int p = -target; p <= target; p ++)
                {
                    int prev = k + p;
                    prev = min(prev, MaxNum - 1);
                    prev = max(prev, 0);
                    
                    dp[i][k] = min(dp[i][k], cost + dp[i - 1][prev]);
                }
            }
        }

        return *min_element(dp.back().begin(), dp.back().end());
    }
};