lintcode91. 最小调整代价动态规划

末蓝、 2023-07-04 14:08 25阅读 0赞

给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

样例
    样例 1:
    	输入:  [1,4,2,3], target=1
      输出:  2
    
    样例 2:
    	输入:  [3,5,4,7], target=2
    	输出:  1
    	
    注意事项
    你可以假设数组中每个整数都是正整数，且小于等于100。

思路：  
dp【i】【j】表示0~i个数中，当取 j 时需要的调整代价。  
dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i-1\]\[k\]+dif);表示在确定0~i在取值为j的情况下，0到i-1范围可以供取的数

class Solution {
        
    public:
        /*
         * @param A: An integer array
         * @param target: An integer
         * @return: An integer
         */
        int MinAdjustmentCost(vector<int> &A, int target) {
        
            // write your code here
            int n=A.size();
            if(n<2) return 0;
            vector<vector<int>> dp(n,vector<int>(101,INT_MAX));
            for (int i = 1; i < 101; i++) {
        
                /* code */
                dp[0][i]=abs(i-A[0]);
            }
            for(int i = 1; i < n; i++)
            {
        
                for(int j = 1; j < 101;j++)
                {
        
                    dp[i][j]=INT_MAX;
                    int dif=abs(j-A[i]);
                    int end=min(100,j+target);
                    int start=max(1,j-target);
                    for(int k = start; k <= end; k++)
                    {
        
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+dif);
                    }
                }
            }
            int mins=INT_MAX;
            for (int i = 1; i < 101 ; i++) {
        
                /* code */
                mins=min(mins,dp[n-1][i]);
            }
            return mins;
        }
    };