9.6腾讯笔试第5题红黑棋
这道题目测是动态规划，但是不好证明算法的正确性。
考虑从左往右放棋子，dp[i][j]表示放i个棋子，其中j个红棋，i-j个黑棋，并且这些红棋和黑棋都递增的最小移动步数，这里猜测剩余还没有考虑的棋子的顺序一定是确定的，否则dp的解法是错误的。那么剩余没摆放的棋子的序列是什么，应该就是原序列删除前j个红棋和前i-j个黑棋的序列，这里把这些棋挪到最前面，剩余棋子的相对顺序应该是不变的，如果变化了，那么保持不变可减少几步移动，这里出题人应该有严格证明。
接下来就是考虑dp转移了，在dp[i][j]状态上，下一个要放的棋子要么是j+1红棋，或者i-j+1黑棋，因此状态会转移到dp[i+1][j+1]和dp[i+1][j],转移代价是多少，就是剩余序列中第j+1红棋和i-j+1黑棋移动到下标i+1的距离，因为这里状态已经是O(n^2)的复杂度，所以转移的复杂度必须是O(1)，所以要预处理r[i][j]，b[i][j]表示前i小红棋和前j小黑棋都移动到最前面，剩余序列第i+1红棋所在位置和第j+1黑棋所在位置，这里红黑分开处理；比如考虑第i+1红棋所在位置，那么原序列中比i+1大的红棋必然在红棋前面，这个直接统计一下，剩下就是看原序列中比j大的黑棋，j从大到小枚举，也就是算r[i][n],r[i][n-1],...,r[i][1], 由于j从大到小递减，那么r的值肯定是递增的，这里自己想一下，很难描述。
#腾讯##笔试题目#
投递好未来等公司8个岗位 >