这个递归算法有什么问题？

Question

问题陈述：

N 元素排列是来自集合 {1, 2, ...,n} 的不同数字的 N 元素序列。例如序列 2,1,4,5,3 是一个 5 元素排列。 P 是 N 元素排列。你的任务是按升序对 P 进行排序。但是因为它非常简单，所以我为您准备了一条新规则。你有两个序列 P 和 Q。P 是一个 N 元素排列，Q 最初是空的，通过对 P 排序形成（即最终 Q = 1, 2, 3, ... , N）。你必须执行 N 步来对 P 进行排序。在第 i 步中，P 有 N-i+1 个剩余元素，Q 有 i-1 个元素，你必须选择第 x 个元素（从 N-i+ P的1个可用元素），放到Q的左边或右边。这一步的代价等于x * i。总成本是各个步骤的成本之和。 N步之后，Q一定是升序。你的任务是最小化总成本。

输入

输入文件的第一行是T（T≤10），测试用例的数量。然后是 T 测试用例的描述。每个测试用例的描述由两行组成。第一行包含一个整数 N (1 ≤ N ≤ 1000)。第二行包含来自集合 {1, 2, .., N} 的 N 个不同的整数，N 元素排列 P.

输出

对于每个测试用例，你的程序应该写一行，包含一个整数——排序的最小总成本。

输入： 1个 4个 4 1 3 2

输出： 15

我的解决方案：

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int sz;
int n[1001];
map<int,int>pos;
int solve(int i,int a,int b){
if(a==-1&&b==sz) //if all the elements have been moved 
    return 0;
if(i>sz)
    return INT_MAX;
    int ret = INT_MAX;
    if(a>=0) //select the element from left
        ret = min(ret,solve(i+1,a-1,b)+((i+1)*pos[n[a]]));
    if(b<sz) //select the element from right
        ret = min(ret,solve(i+1,a,b+1)+((i+1)*pos[n[b]]));
return ret;
}

int main()
{
   int t;
   cin>>t;
   while(t--){
        cin>>sz;
   for(int i=0;i<sz;i++){
    int x;
    cin>>x;
    n[i] = x; //value
    pos[x] = i+1; //position of elements of array before sorting
   }
   sort(n,n+sz); //sorting the array
   int ret = INT_MAX;
   for(int i=0;i<sz;i++)  
     ret= min(ret,solve(0,i,i+1));
             cout << ret << endl;

        }
    return 0;
}

这个returns错误的答案。我的方法有什么问题？这怎么能解决？

Answer 1

一个问题是您正在根据 pos[n[a]] 计算成本。

pos[n[a]] returns原数组中的位置，但代价应该是基于当前数组P中的位置（即一些元素移动到Q）。

比如P本来是{4,1,2}那么2的位置就是x==3，但是P降为{1,2}之后2的位置就是x==2.

这个递归算法有什么问题？

What's wrong in this recursive algorithm?

c++

algorithm

sorting

dynamic-programming

memoization