当前位置：网站首页>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 .
边栏推荐
- El form item regular verification
- 光环效应——谁说头上有光的就算英雄
- 学会使用LiveData和ViewModel，我相信会让你在写业务时变得轻松
- Scheme of printing statistical information in log
- Liu Dui (fire line safety) - risk discovery in cloudy environment
- "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
- 我们该如何保护自己的密码？
- Six years of technology iteration, challenges and exploration of Alibaba's globalization and compliance
- In depth cooperation | Taosi data cooperates with changhongjia Huawei customers in China to provide tdengine with powerful enterprise level products and perfect service guarantee
- Go整合Logrus实现日志打印
猜你喜欢
Enter the top six! Boyun's sales ranking in China's cloud management software market continues to rise
既不是研发顶尖高手，也不是销售大牛，为何偏偏获得 2 万 RMB 的首个涛思文化奖？
清华章毓晋老师新书：2D视觉系统和图像技术（文末送5本）
sqlilabs less-11~12
Phpcms realizes the direct Alipay payment function of orders
队列的基本操作(C语言实现)
被裁三個月，面試到處碰壁，心態已經開始崩了
Etcd 概要 机制 和使用场景
QT社团管理系统
开源实习经验分享：openEuler软件包加固测试
随机推荐
The integration of computing and Internet enables the transformation of the industry, and the mobile cloud lights up a new roadmap for the future of digital intelligence
[241. Design priority for operation expression]
[sword finger offer] 55 - I. depth of binary tree
sqlilabs less-11~12
Dragon lizard community open source coolbpf, BPF program development efficiency increased 100 times
WebSocket(简单体验版)
SWT / anr problem - how to open binder trace (bindertraces) when sending anr / SWT
用对场景，事半功倍！TDengine 的窗口查询功能及使用场景全介绍
[IOT design. Part I] stm32+ smart cloud aiot+ laboratory security monitoring system
Liu Dui (fire line safety) - risk discovery in cloudy environment
当你真的学会DataBinding后，你会发现“这玩意真香”!
6年技术迭代，阿里全球化出海＆合规的挑战和探索
How to pass array parameters in get request
小程序- view中多个text换行
What class loading mechanisms does the JVM have?
SWT／ANR问题－－当发送ANR/SWT时候如何打开binder trace(BinderTraces)
当主程架构游戏的时候，防止到处调用减少耦合性，怎么开放接口给其他人调用呢？
佩服，阿里女程序卧底 500 多个黑产群……
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?
SWT／ANR问题－－如何捕获性能的trace