白天不懂夜的黑

来提每日一题 2024-10-18 13:13:23
蒲公英优质笔记激励计划2.0 转码 每天59秒拿下每日一题 每日一题 创作灵感 LeetCode 刷题 近期找工作现状 程序员 国区每日一题今日思路: 记忆化搜索。记memo[i][j]为perm[0,..i]恰好有j个逆数对的数目,这里不需要考虑第i个位置所填写的数字,假设第i个位置填第k大数,那么这个数与前面组成k-1个逆数对。对于每一个位置存在两种情况,当前位置存在限制arr[i],这时只能选择dp(i, arr[i])种组合,这里隐含着两个条件,arr数组必须非递减,同时当前j与上一个位置的差值不超过i,因为i位置最多贡献i个逆数对;另一种情况是不存在限制,这时可以任意选择逆数对数目,只需要不超过i和j的较小者。递归终点i为0说明找到一种可行方案。最终答案为dp(n-1,arr[n-1])。 国际站每日一题今日思路: 贪心。将数字转换为字符串,这样便于操作每一数位,模拟所以交换可能,找到最大值。看到这点个赞吧

0 阅读:0
来提每日一题

来提每日一题

感谢大家的关注