当前位置：网站首页>Summary of leetcode's dynamic programming 5
Summary of leetcode's dynamic programming 5
2022-07-01 14:09:00 【nuist__ NJUPT】
leetcode Summary of dynamic programming 5
1- The smallest of two strings ASCII Delete and
Topic link ： The title link is here ！！！
Ideas ： Dynamic programming
dp[i][j] Said to i-1 a null-terminated string s1 And with j-1 a null-terminated string s2 Keep the same deleted minimum ASCII character .
initialization dp Array
If one of them is an empty string , In order to keep them the same , You need to delete all the characters of another .
If s1.charAt(i-1)==s2.charAt(j-1), You don't need to delete , The recurrence formula is as follows ：
dp[i][j] = dp[i-1][j-1]
otherwise , You need to delete one of the two ASCII Small , Recursive down ：
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;
AC The code is as follows ：
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int [][] dp = new int [s1.length()+1][s2.length()+1] ;
for(int i=1; i<=s1.length(); i++){
dp[i][0] = dp[i-1][0] + s1.charAt(i-1) ;
}
for(int j=1; j<=s2.length(); j++){
dp[0][j] = dp[0][j-1] + s2.charAt(j-1) ;
}
for(int i=1; i<=s1.length(); i++){
for(int j=1; j<=s2.length(); j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] ;
}else{
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;
}
}
}
return dp[s1.length()][s2.length()] ;
}
}
2- Delete and get points
Topic link ： The title link is here ！！！
Ideas ： take nums The array becomes the sum of each number , Then it becomes the problem of house raiding , You can only choose between stealing and not stealing every time .
class Solution {
public int deleteAndEarn(int[] nums) {
int [] value = new int [10001] ;
int [] dp = new int [value.length] ;
for(int i=0; i<nums.length; i++){
value[nums[i]] += nums[i] ;
}
dp[0] = value[0] ;
dp[1] = Math.max(value[0],value[1]) ;
for(int i=2; i<value.length; i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+value[i]) ;
}
return dp[dp.length-1] ;
}
}
3- Rotate the numbers
Topic link ： The title link is here ！！！
Ideas 1： Judge whether it is a good number , If yes , Then add 1
Satisfying the following two is a good number ：
1- It doesn't contain 3,4,7 One of them
2- contain 2,5,6,9 One of them
class Solution {
public int rotatedDigits(int n) {
int cnt = 0 ;
for(int i=1; i<=n; i++){
if(goodNumder(i)){
cnt ++ ;
}
}
return cnt ;
}
public boolean goodNumder(int n){
String str = String.valueOf(n) ;
boolean flag = false ;
for(int i=0; i<str.length(); i++){
if(str.charAt(i)=='3' || str.charAt(i)=='4' || str.charAt(i)=='7'){
return false ;
}else if(str.charAt(i)=='2' || str.charAt(i)=='5' || str.charAt(i)=='6' || str.charAt(i)=='9'){
flag = true ;
}
}
return flag ;
}
}
4- The longest Fibonacci subsequence length
Topic link ： The title link is here ！！！
Ideas ：dp[i][j] From i To j The longest Fibonacci sequence of positions , use map Store the corresponding elements and subscripts , If each group (3 A digital ) The first number of Fibonacci appears , Update dp Array .
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length ;
if(n<3){
return 0 ;
}
Map<Integer,Integer> map = new HashMap<>() ;
for(int i=0; i<n; i++){
map.put(arr[i],i) ;
}
int [][] dp = new int [n][n] ;
int res = 0 ;
for(int i=0; i<n;i++){
for(int j=0; j<i; j++){
if(map.containsKey(arr[i]-arr[j]) && arr[i]-arr[j]<arr[j]){
int k = map.get(arr[i]-arr[j]) ;
dp[j][i] = Math.max(dp[k][j]+1,dp[j][i]) ;
dp[j][i] = Math.max(dp[j][i],3) ;
}
res = Math.max(res, dp[j][i]) ;
}
}
return res ;
}
}
5- The best time to buy and sell stocks includes handling fees
Topic link ： The title link is here ！！！
Ideas ： The first i There are two states in heaven , Holding or not holding shares
If holding shares , Then it can be divided into two situations ：1- Held the day before ,2- Buy today
If you do not hold shares , There are also two situations ：1- Didn't hold... The day before ,2- Sell today
We finally found that we didn't hold it in turn , That's our answer
dp[i][1]: It means the first one i Day holding
dp[i][0]: It means the first one i Days don't hold
class Solution {
public int maxProfit(int[] prices, int fee) {
int [][] dp = new int [prices.length][2] ;
dp[0][0] = 0;
dp[0][1] = -prices[0] ;
for(int i=1;i<prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee) ;
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]) ;
}
return dp[dp.length-1][0] ;
}
}
6- The descent path is the smallest and
Topic link ： The title link is here ！！！
Ideas ： Bottom up , Put the smallest of the three below each time , Add to top , Finally, the smallest in the first line is the minimum sum of the descent path .
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length ;
for(int row=n-2; row>=0; row--){
for(int col=0; col<n; col++){
int value = matrix[row+1][col] ;
if(col-1>=0){
value = Math.min(matrix[row+1][col-1],value) ;
}
if(col+1<n){
value = Math.min(matrix[row+1][col+1],value) ;
}
matrix[row][col] += value ;
}
}
int ans = Integer.MAX_VALUE ;
for(int res : matrix[0]){
ans = Math.min(ans, res) ;
}
return ans ;
}
}
7- Number of combinations IV
Topic link ： The title link is here ！！！
Ideas ：dp[x]: The sum of the selected elements is equal to x Number of alternatives .
class Solution {
public int combinationSum4(int[] nums, int target) {
int [] dp = new int [target+1] ;
dp[0] = 1 ;
for(int i=0; i<=target; i++){
for(int num : nums){
if(i-num>=0){
dp[i] += dp[i-num] ;
}
}
}
return dp[target] ;
}
}
8- The best time to buy and sell stocks IV
Topic link ： The title link is here ！！！
Ideas ： Dynamic programming
We use it buy[i][j] For an array prices[0…i] In terms of price , Proceed exactly j transaction , And currently holds a stock , The maximum profit in this case ; use sale[i][j] It means that j transaction , And does not currently hold shares , The maximum profit in this case .
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length ;
if(n==0){
return 0;
}
int [][] buy = new int [n][k+1] ;
int [][] sale = new int [n][k+1] ;
buy[0][0] = -prices[0] ;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sale[0][i] = Integer.MIN_VALUE / 2;
}
for(int i=1; i<n; i++){
buy[i][0] = Math.max(buy[i-1][0],sale[i-1][0]-prices[i]) ;
for(int j=1; j<=k; j++){
buy[i][j] = Math.max(buy[i-1][j],sale[i-1][j]-prices[i]) ;
sale[i][j] = Math.max(sale[i-1][j],buy[i-1][j-1]+prices[i]) ;
}
}
int max = Integer.MIN_VALUE ;
for(int sell : sale[n-1]){
max = Math.max(sell,max) ;
}
return max ;
}
}
9-01 matrix
Topic link ： The title link is here ！！！
Ideas ： Recursion from the upper left corner and the lower right corner .
The recursive expression is as follows ：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length ;
int n = mat[0].length ;
int [][] dp = new int [m][n] ;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
dp[i][j] = (mat[i][j] == 0 ? 0 : Integer.MAX_VALUE/2);
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i-1>=0){
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1) ;
}
if(j-1>=0){
dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1) ;
}
}
}
for(int i=m-1; i>=0; i--){
for(int j=n-1; j>=0; j--){
if(i+1<m){
dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1) ;
}
if(j+1<n){
dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1) ;
}
}
}
return dp ;
}
}
10- Divisor game
Topic link ： The title link is here ！！！
Ideas ： We define dp[i] Represents the current number i Whether the first hand is in the state of winning or losing ,}true The first to win ,alse It means that the first hand will lose , Recursion after going , If the state after taking a number is inevitable , Then the current state must be winning .
class Solution {
public boolean divisorGame(int n) {
if(n==1){
return false ;
}
if(n==2){
return true ;
}
boolean [] dp = new boolean[n+1] ;
dp[1]=false ;
dp[2]=true ;
for(int i=3; i<=n; i++){
for(int j=1; j<i; j++){
if((i%j)==0 && !dp[i-j]){
dp[i] = true ;
break ;
}
}
}
return dp[n] ;
}
}
No silicon step , A thousand miles , Don't product the little stream , Nothing can be a river .
边栏推荐
- leetcode622. Design cycle queue (C language)
- 学会使用LiveData和ViewModel，我相信会让你在写业务时变得轻松
- What class loading mechanisms does the JVM have?
- sqlilabs less13
- 【R语言数据科学】：机器学习常见评估指标
- How can we protect our passwords?
- Self cultivation of open source programmers who contributed tens of millions of lines of code to shardingsphere and later became CEO
- 【修复版】仿我爱看电影网站模板/海洋CMS影视系统模板
- Open source internship experience sharing: openeuler software package reinforcement test
- 光环效应——谁说头上有光的就算英雄
猜你喜欢
QT学习管理系统
sqlilabs less10
Fiori 应用通过 Adaptation Project 的增强方式分享
What "hard core innovations" does Intel have in the first half of 2022? Just look at this picture!
When you really learn databinding, you will find "this thing is really fragrant"!
Build your own website (21)
使用CMD修复和恢复病毒感染文件
Play with mongodb - build a mongodb cluster
Etcd summary mechanism and usage scenarios
2022年PMP项目管理考试敏捷知识点（6）
随机推荐
3.4 data query in introduction to database system - select (single table query, connection query, nested query, set query, multi table query)
C language course design topic
微服务大行其道的今天，Service Mesh是怎样一种存在？
"National defense seven sons" funding soared, with Tsinghua reaching 36.2 billion yuan, ranking second with 10.1 billion yuan. The 2022 budget of national colleges and universities was made public
Why did you win the first Taosi culture award of 20000 RMB if you are neither a top R & D expert nor a sales Daniel?
Kongsong (Xintong Institute) - cloud security capacity building and trend in the digital era
使用net core 6 c＃ 的 NPOI 包，读取excel..xlsx单元格内的图片，并存储到指定服务器
玩转MongoDB—搭建MongoDB集群
Basis of target detection (NMS)
用对场景，事半功倍！TDengine 的窗口查询功能及使用场景全介绍
开源实习经验分享：openEuler软件包加固测试
既不是研发顶尖高手，也不是销售大牛，为何偏偏获得 2 万 RMB 的首个涛思文化奖？
TexStudio使用教程
百度上找的期货公司安全吗?期货公司怎么确定正规
2. Sensor size "recommended collection"
When the main process architecture game, to prevent calls everywhere to reduce coupling, how to open the interface to others to call?
sqlilabs less13
那个很努力的学生，高考失败了……别慌！你还有一次逆袭机会！
El form item regular verification
【修复版】仿我爱看电影网站模板/海洋CMS影视系统模板