每日一题|【每日一题】只有两个键的键盘（dp、数学）, LIS问题变种（最长递增子序列的个数（dp+二分 nlogn））动态规划|算法

【每日一题|【每日一题】只有两个键的键盘（dp、数学）, LIS问题变种（最长递增子序列的个数（dp+二分 nlogn））】
文章目录

650 只有两个键的键盘（dp、数学）
LIS问题变种：最长递增子序列的个数（dp+二分 nlogn）

650 只有两个键的键盘（dp、数学）

每日一题|【每日一题】只有两个键的键盘（dp、数学）, LIS问题变种（最长递增子序列的个数（dp+二分 nlogn））

文章图片

一道dp的题目，但是美妙之处在于这道题有数学解法。
首先对于dp的思路，dp[i]表示 i 个字符时候的最小次数，dp[i] = dp[i/j]+j 得到转移方程。一个小优化在于，因为是找的因子，i/j * j = i 因此我们枚举到 i \sqrt{i} i ?就可以了。
更为巧妙的数学解法是，进行拆分的时候肯定 a1*a2*a3 = n 一定是要找到因子的。而实际的代价是 a1+a2+a3 考虑到a1*a2>=a1+a2。因此，我们其实找到全部质因子就可以

class Solution {public int minSteps(int n) {int ans = 0; // 分解质因数，但是这里其实不是最佳的。 for(int i = 2; i*i<=n; i++){while(n%i ==0){n /= i; ans += i; } } // 最后剩余了一个质数 if(n>1) ans += n; return ans; ================================================= int[] dp = new int[n+1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[1] = 0; for (int i = 2; i<=n; i++){// 这里其实可以找到两个因子 j和i/j; for(int j = 1; j*j<=i; j++){if (i%j == 0){dp[i] = Math.min(dp[i], dp[j]+i/j); dp[i] = Math.min(dp[i], dp[i/j]+j); } } } return dp[n]; } }

LIS问题变种：最长递增子序列的个数（dp+二分 nlogn）

文章图片

LIS问题是非常经典的问题了，如果要求解寻找最长递增子序列的长度，可以nlogn，这个不难。
这个题目是升级版本，要求得到最长子序列的个数。需要更加复杂的dp+二分了。
当然我们可以使用简单的 n 2 n^2 n2的方法，维护一个cnt[i]表示使用 i 得到最长序列的种类数，dp[i]表示以 i 结尾的最长序列。

class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length, maxLen = 0, ans = 0; int[] dp = new int[n]; int[] cnt = new int[n]; for (int i = 0; i < n; ++i) {dp[i] = 1; cnt[i] = 1; for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1; cnt[i] = cnt[j]; // 重置计数 } else if (dp[j] + 1 == dp[i]) {cnt[i] += cnt[j]; } } } if (dp[i] > maxLen) {maxLen = dp[i]; ans = cnt[i]; // 重置计数 } else if (dp[i] == maxLen) {ans += cnt[i]; } } return ans; } }

更优的，我们考虑一个nlogn的方法 dp.get(i).get(j) 表示长度为 i 的第 j 种可能。这里需要注意，如果是从前往后遍历的话，其实很容易发现，这个dp.get(i)一定是单调不增的，否则一定可以增加长度。

例子我们可以假想插入 4.5 和5 [1,3,5,4,7] 1/ 1 2/ 3 3/ 5 4 4/ 7

cnt[i][j] 是前缀和的思想，表示长度为 i 的时候，前 j 个元素作为结尾的全部可能数量。当我们遍历到 nums 的某个数字的时候，查看dp每个list的最后一个数字（因为是最小的）。如果大于，说明可以这个list里面起码有小于的当前数字的。假设是k。
然后我们可以二分的找到 dp.get(k) 种的边界 p (第一个小于 nums[i] 的数字)，在 p 之后的数字都是小于 numus[i] 的。因此 nums[i] 和这些数字可以组成长度为k+1的序列，而这些数字的可能数量是 newadd = cnt.get(k).get(size()-1) - cnt.get(k).get(p)
最后在

dp.get(k+1).add(nums[i]) ;
 cnt.get(k+1).add(last+1)

class Solution {public int findNumberOfLIS(int[] nums) {// 如果是n2的方法，就是暴力dp List> dp = new ArrayList<>(); List> cnt = new ArrayList<>(); int n = nums.length; for(int i = 0; i= 0){int p = findInList(dp.get(k), nums[i]); int size = cnt.get(k).size(); newadd = cnt.get(k).get(size-1)-cnt.get(k).get(p); } if(k == dp.size()-1){dp.add(new ArrayList()); cnt.add(new ArrayList()); cnt.get(k+1).add(0); dp.get(k+1).add(nums[i]); cnt.get(k+1).add(newadd); }else{dp.get(k+1).add(nums[i]); int cntSize = cnt.get(k+1).size(); cnt.get(k+1).add(cnt.get(k+1).get(cntSize-1)+newadd); } } int size = cnt.size(); int lastszie = cnt.get(size-1).size(); return cnt.get(size-1).get(lastszie-1); } // 返回的是最后一个元素一定小于的，且再大就一定大于等于的。 public int findList(List> dp, int target){int n = dp.size(); int l = 0; int r = n-1; while(l<=r){int mid = l+(r-l)/2; int size = dp.get(mid).size(); int cur = dp.get(mid).get(size-1); if (cur>target){r = mid-1; }else if (cur < target){l = mid+1; }else{return mid-1; } } return r; } // 返回小于的第一个 public int findInList(List nums, int target){int n = nums.size(); int l = 0; int r = n-1; while(l<=r){int mid = l+(r-l)/2; int cur = nums.get(mid); if (cur>target){l = mid+1; }else if (cur < target){r = mid-1; }else{l = mid+1; } } return l; } }