Open nagato1208 opened 5 years ago
https://nagato1208.github.io/2019/09/08/leetcode-1187-Make-Array-Strictly-Increasing-DP/
描述给两个数组arr1和arr2, 里面的数字都是正整数. 可以用arr2中的数字替换掉arr1中的任意数字(不限次数), 问最少多少次替换能够将arr1改变成严格递增数组. 思路最长递增子串, bottom-up找LIS的长度很简单… 如果问最少修改多少个数组元素, 使得原数组严格递增呢?思路是开一个数组LIS, LIS[i]表示以下标i结尾的有效的最长递增子序列长度. 有效指的是我们可以修改i
https://nagato1208.github.io/2019/09/08/leetcode-1187-Make-Array-Strictly-Increasing-DP/
描述给两个数组arr1和arr2, 里面的数字都是正整数. 可以用arr2中的数字替换掉arr1中的任意数字(不限次数), 问最少多少次替换能够将arr1改变成严格递增数组. 思路最长递增子串, bottom-up找LIS的长度很简单… 如果问最少修改多少个数组元素, 使得原数组严格递增呢?思路是开一个数组LIS, LIS[i]表示以下标i结尾的有效的最长递增子序列长度. 有效指的是我们可以修改i