PDD面试官：请你聊聊简历上写的动态规划思想的思路与实现

众所周知，想要成为一名程序员，绕不开算法训练这一关，训练算法不仅有助于提升我们代码编写的质量，还能帮助我们理解框架源码，常见API的实现原理。近日，我就在工作日中，运用了算法的常见思想——动态规划，解决了一个问题。

背景

公司的后台管理中有一个功能模块要求，用户可以在列表页面进行拖拽排序，看似非常简单的功能，我却遇到了困难，领导要求后端的同事减少接口数量，降低维护成本，取消了之前通过传参排序号对列表重新排序的接口，只保留了常规的新增与编辑接口。根据现有的条件，我想到只要能获得用户选中的位置发生变化的数据，将它的排序号取其两旁数据排序号的中间值就行了，但是在调用公司基于element-ui封装的表格组件中的排序API时出现了问题......

通过调用sw-table（表格组件）的dragHandle方法时，其返回值是一个已经排序完的数组，无法获取用户是选中哪一条数据进行了排序，顺着这个思路，我翻阅了公司的组件库文档和封装sw-table的源码，是有找到获取用户点击某一行的数据信息，但是无法获取到该数据位置发生改变过后的信息，在比较之后，我决定还是从dragHandle这一方法上入手。

排序操作

dragHandle的返回结果

drangHandle的内部源码

思考

根据dragHandle返回已经排序好的数组，罗列其排序号，其中最长连续递增的子序列可以理解为已经排序好的一串的序列，而另外一组不是以递增排序好的序列，其排序号需要重新赋值，赋值的规则如下：

假设有序序列的最小下标为min，最大下标为max。

1. 如果有序序列是从数组的中间部分（不到头部）到尾部，那么无序序列必然从下标为0的元素开始至下标min - 1结束，无序序列的排序号需要保持递增并且最大排序号不能超过有序序列的最小排序号。

2. 如果有序序列是从数组的头部间部分到中间部分（不到尾部），那么无序序列必然从下标为max + 1的元素开始至下标为数组长度减一结束，无序序列的排序号需要保持递增并且最小排序号不能小于有序序列的最大排序号。

随后在采用Promise.all()的方法，将排序号发生变化的数据依次调用保存接口更改排序号即可。

根据上述的思路，我就想到了最长连续递增子序列的相关算法思想——动态规划去解决。

解决

首先，让我们看一下什么是动态规划：

动态规划（Dynamic Programming）是一种解决多阶段决策过程最优化问题的数学方法。它将问题分解成若干个子问题，通过递推的方式求解这些子问题，并将其结果存储起来，以避免重复计算，从而达到减少时间复杂度的目的。

动态规划常见的解决步骤如下：

*确定问题的状态：即确定问题需要由哪些变量来描述。*
*定义状态转移方程：根据问题的最优子结构性质，定义出状态之间的转移关系。*
*确定边界条件：即确定最小规模的子问题的解，通常是初始状态。*
*通过递推求解问题：按照状态转移方程，从边界条件开始逐步求解更大规模的子问题，直至达到所求问题的规模*。

根据如上的步骤，我去leetcode上找相关算法题，用动态规划的思想去实现了一遍：leetcode.cn/problems/lo…

以下是解决的代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    // 采用动态规划思想，
    // 首先对dp进行初始化值，单个元素也可以视为长度为一的最长递增连续子序列
    // 递推关系为 dp[i] = dp[i - 1] + 1;
    let dp = new Array(nums.length)
    dp = dp.fill(1);
    let maxLen = 1;
    for(let i = 1;i < nums.length; i++){
        if(nums[i] > nums[i - 1]){
            dp[i] = dp[i - 1] + 1;
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen
};

根据上述代码的思路，再结合遇到的问题，编写出了如下的代码：

async dragHandle(val){
    let copyArr = JSON.parse(JSON.stringify(val))
    let min = 0 ,max = copyArr.length - 1;
    let res = []
    // 寻找最长的递增子序列
    let dp = new Array(copyArr.length)
    dp = dp.fill(1);
    let maxLen = 1;
    for(let i = 1;i < copyArr.length; i++){
        if(copyArr[i].sortNumber > copyArr[i - 1].sortNumber){
            dp[i] = dp[i - 1] + 1;
        }
        if(dp[i] !== maxLen){
            maxLen = Math.max(maxLen, dp[i]);
            if(maxLen >= Math.floor(copyArr.length / 2)){
                min = i;
                max = copyArr.length - 1;
            }else{
                min = 0;
                max = i;
            }
        }
    }
    // 判断乱序序列是从那一部分开始的
    if(min === 0){
        let tempArr = copyArr.slice(max + 1, copyArr.length);
        // 对排序号重新赋值
        tempArr.forEach((item, index)=>{
            if(index === 0){
                item.sortNumber = copyArr[max].sortNumber + 1;
            }else{
                item.sortNumber = tempArr[index - 1].sortNumber + 1;
            }
            res.push(item)
        })
    }else if(max === copyArr.length -1){
        let tempArr = copyArr.slice(0, min)
        tempArr.forEach((item, index)=>{
            item.sortNumber = copyArr[min].sortNumber + index - min;
            res.push(item);
        })
    }
    // 
    Promise.all(res.map((item)=>{
        return new Promise(async (resolve,reject)=>{
            item.terminalInfo = item.terminalInfo ? item.terminalInfo.split(',') : item.terminalInfo;
            item.indexId = item.id;
            const res = await saveIndex(item);
            res.code === 0 ? resolve() : reject()
        })
    })).then(()=> {
        this.getIndexTableData();
        this.$message({
            type: 'success',
            message: '排序成功'
        })
    }).catch(()=>{
        this.$message.error('排序错误')
    })
},

总结

综上，通过本次实践，让我学到了如何从各种角度找到解决的方案，根据实际情况选出最优方案，也让我学会如何运用算法的思想去解决工作中遇到的难题，做到学以致用，更让我理解了动态规划的核心思想，让我在以后遇到类似问题时，能想出大致的思路（但是动态规划还是好难......）