Weighted Job Scheduling

Problem

Given N jobs where every job is represented by following three elements of it.

Start Time
Finish Time
Profit or Value Associated
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Code

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int n;
struct Job {
    int start;
    int end;
    int profit;
}job[N];
bool cmp(const Job & a,const Job & b) {
    return a.end < b.end;
}
int dp[N];

int search(int end,int pos) {
    if (job[0].end > end) {
        return -1;
    }
    int l = 0;
    int r = pos + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (job[m].end <= end) {
            l = m + 1;
        }
        else {
            r = m;
        }
    }
    return l - 1;
}

int main() {
 scanf("%d",&n);
 for (int i = 0;i < n;i ++) {
     scanf("%d%d%d",&job[i].start,&job[i].end,&job[i].profit);
 }
 sort(job,job + n,cmp);
 dp[0] = job[0].profit;
 for (int i = 1;i < n;i ++) {
     dp[i] = dp[i - 1];
     int pos = search(job[i].start,i - 1);
     if (pos != -1) {
         dp[i] = max(dp[i],dp[pos] + job[i].profit);
     }
 }
 cout << dp[n - 1] << endl;
 return 0;
}

How to print maximum number of A’s using given four keys

Problem

Key 1:  Prints 'A' on screen
Key 2: (Ctrl-A): Select screen
Key 3: (Ctrl-C): Copy selection to buffer
Key 4: (Ctrl-V): Print buffer on screen appending it
after what has already been printed. 

Solution
   a) For N < 7, the output is N itself. b) Ctrl V can be used multiple times to print current buffer (See last two examples above). The idea is to compute the optimal string length for N keystrokes by using a simple insight. The sequence of N keystrokes which produces an optimal string length will end with a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V's (For N > 6). //from geeks.

Code

#include <stdio.h>
#include <iostream>
using namespace std;

int T;
int n;
const int N = 85;
typedef long long ll;
ll dp[N];
int main() {
 for (int i = 1;i <= 6;i ++) {
     dp[i] = i;
 }
 for (int i = 7;i <= 75;i ++) {
     for (int j = 1;j <= i - 3;j ++) {
         dp[i] = max(dp[i],dp[j] * (1 + i - j - 2));
     }
 }
 scanf("%d",&T);
 while (T --) {
     scanf("%d",&n);
     cout << dp[n] << endl;
 }
 return 0;
}

Maximum profit by buying and selling a share at most twice

Problem

   In a daily share trading, a buyer buys shares in the morning and sells it on same day. If the trader is allowed to make at most 2 transactions in a day, where as second transaction can only start after first one is complete (Sell->buy->sell->buy). Given stock prices throughout day, find out maximum profit that a share trader could have made.

Code

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 110;
int n;
int a[N];
int dp[N];
int main() {
    scanf("%d",&n);
    for (int i = 0;i < n;i ++) {
        scanf("%d",&a[i]);
    }
    memset(dp,0,sizeof(dp));
    int max_val = a[n - 1];
    for (int i = n - 2;i >= 0;i --) {
        dp[i] = max(dp[i + 1],max_val - a[i]);
        max_val = max(max_val,a[i]);
    }
    
    int min_val = a[0];
    for (int i = 1;i < n;i ++) {
        dp[i] = max(dp[i - 1],a[i] - min_val + dp[i]);
        min_val = min(min_val,a[i]);
    }
    cout << dp[n - 1] << endl;
}

Compute sum of digits in all numbers from 1 to n

Problem

   Given a number x, find sum of digits in all numbers from 1 to n.

Solution
     take 389 for example;
     count[1,299) + [300,389)'s 3 + [1,89)
Code

#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;


int f(int n) {
    if (n < 10) {
        return n * (n + 1) / 2;
    }
    
    int d = log10(n);
    
    int a[15];
    a[1] = 45;
    for (int i = 2;i <= d;i ++) {
        a[i] = a[i - 1] * 10 + 45 * pow(10,i - 1);
    }
    int p = ceil(pow(10,d));
    
    int msd = n / p;
    
    int p1 = msd * a[d] + (msd * (msd - 1)) / 2 * p;
    //int p1 = f(msd * p - 1);
    int p2 = msd * (n % p + 1) + f(n % p);
    return p1 + p2;
}

int main() {
 //code
 cout << f(389) << endl;
 return 0;
}

Collect maximum points in a grid using two traversals

Problem

   Given a matrix where every cell represents points. How to collect maximum points using two traversals under following conditions?
1) The first traversal starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (R-1, 0). The second traversal starts from top right corner, i.e., (0, C-1) and should reach bottom right corner, i.e., (R-1, C-1)/

2) From a point (i, j), we can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

3) A traversal gets all points of a particular cell through which it passes. If one traversal has already collected points of a cell, then the other traversal gets no points if goes through that cell again.

Solution
     check bound at first is much easier.
Code

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
const int R = 55;
const int C = 55;
int dp[R][C][C];
int a[R][C] = {{3, 6, 8, 2},
         {5, 2, 4, 3},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         };
int n,m;

int dfs(int row,int c1,int c2) {
    if (c1 < 0 || c1 >= m || c2 < 0 || c2 >= m) return -0x3f3f3f3f;
    if (row == n - 1 && c1 == 0 && c2 == m - 1) {
        return a[row][c1] + a[row][c2];
    }
    if (row == n - 1) return -0x3f3f3f3f;
    if (dp[row][c1][c2] != -1) return dp[row][c1][c2];
    int add = 0;
    if (c1 == c2) {
        add = a[row][c1];
    }
    else {
        add = a[row][c1] + a[row][c2]; 
    }
    
    int ans = -0x3f3f3f3f;
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1,c2));
    ans = max(ans,add + dfs(row + 1,c1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 + 1));
    return dp[row][c1][c2] = ans;
}

int calc() {
    memset(dp,-1,sizeof(dp));
    return dfs(0,0,m - 1);
}

int main() {
    n = 5;
    m = 4;
    cout << calc() << endl;
 return 0;
}

Minimum Points To Reach Destination dp

Problem

   Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. 

Solution
     use bottom-up is much easier than up-bottom;
     and pay attention to that the beginning should has at least 1 point.
Code

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;


const int N = 15;
int T;
int n,m;
int a[N][N];
int dp[N][N];
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d",&n,&m);
        for (int i = 1;i <= n;i ++) {
            for (int j = 1;j <= m;j ++) {
                scanf("%d",&a[i][j]);
            }
        }
        dp[n][m] = a[n][m] > 0 ? 1 : -a[n][m] + 1;
        for (int i = n;i >= 1;i --) {
            for (int j = m;j >= 1;j --) {
                if (i == n && j == m) continue;
                int mins = 0x3f3f3f3f;
                if (i + 1 <= n) {
                    mins = min(mins,dp[i + 1][j]);
                }
                if (j + 1 <= m) {
                    mins = min(mins,dp[i][j + 1]);
                }
                dp[i][j] = max(mins - a[i][j],1);
            }
        }
        cout << dp[1][1] << endl;
    }
}

Mobile Numeric Keypad Problem

Problem
   Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of given length.
Solution
   dynamic programming

Code

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char board[4][3] = {
  {'1','2','3'},
  {'4','5','6'},
  {'7','8','9'},
  {'*','0','#'}
};

const int N = 110;
int dp[N][12];
int dir[5][2] = {0,0,1,0,-1,0,0,1,0,-1};
int main() {
 memset(dp,0,sizeof(dp));
 for (int i = 0;i <= 9;i ++) {
     dp[0][i] = 0;
     dp[1][i] = 1;
 }
 
 for (int i = 2;i <= 100;i ++) {
     for (int j = 0;j < 4;j ++) {
         for (int k = 0;k < 3;k ++) {
             if (board[j][k] == '*' || board[j][k] == '#') continue;
             int num = board[j][k] - '0';
             for (int t = 0;t < 5;t ++) {
                 int dx = j + dir[t][0];
                 int dy = k + dir[t][1];
                 if (dx < 0 || dy < 0 || dx >= 4 || dy >= 3) continue;
                 if (board[dx][dy] == '*' || board[dx][dy] == '#') continue;
                 int nxtnum = board[dx][dy] - '0';
                 dp[i][num] += dp[i - 1][nxtnum]; 
             }
         }
     } 
 }
 
 int n;
 while (cin >> n) {
     int sum = 0;
     for (int i = 0;i <= 9;i ++) {
         sum += dp[n][i];
     }
     cout << sum << endl;
 }
    return 0;
}

Shortest Common Supersequence

Problem
   Given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.

Solution
   str1len + str2len - lcs

Code

#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 110;
int dp[N][N];
string a,b;
int main() {
    cin >> a >> b;
 int n = a.size();
 int m = b.size();
 dp[0][0] = 0;
 for (int i = 1;i <= n;i ++) {
     for (int j = 1;j <= m;j ++) {
         if (a[i] == b[j]) {
             dp[i][j] = dp[i - 1][j - 1] + 1;
         }
         else {
             dp[i][j] = max(dp[i][j - 1],dp[i - 1][j]);
         }
     }
 }
 cout << n + m - dp[n][m] << endl;
 return 0;
}

Consecutive 1's not allowed

Problem
   Count number of binary strings without consecutive 1’s.

Solution
 a[i] means string ends with 0 && not contains  11;
 b[i] means string ends with 1 && not contains 11;
 c[i] means string ends with 11 or contains 11;

Code

#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 75;
long long a[N],b[N],c[N];
int T;
int n;
const int mod = 1e9 + 7;
int main() {
 a[1] = 1;
 b[1] = 1;
 c[1] = 0;
 for (int i = 2;i <= 70;i ++) {
     a[i] = (a[i - 1] + b[i - 1]) % mod;
     b[i] = a[i - 1] % mod;
     c[i] = (2 * c[i - 1] + b[i - 1]) % mod;
 }
 cin >> T;
 int n;
 while (T --) {
     cin >> n;
     cout << (a[n] + b[n]) % mod << endl;
 }
 return 0;
}

Optimal Binary Search Tree

Problem
   Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Solution
    dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j]) + sum[i->j];

Code
   

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 260;
int n;
int a[N];
int sum[N];
int dp[N][N];
int main() {
    while (scanf("%d",&n) != EOF) {
        for (int i = 1;i <= n;i ++) {
            scanf("%d",&a[i]);
        }
        memset(dp,0x3f,sizeof(dp));
        sum[0] = 0;
        for (int i = 1;i <= n;i ++) {
            sum[i] = sum[i - 1] + a[i];
        }

        for (int i = 1;i <= n;i ++) {
            dp[i][i] = 0;
        }
        for (int len = 2;len <= n;len ++) {
            for (int i = 1;i + len - 1 <= n;i ++) {
                int j = i + len - 1;
                for (int k = i;k <= j;k ++) {
                    int tmp = 0;
                    tmp += sum[j] - sum[i - 1] - a[k];
                    tmp += k - 1 >= i ? dp[i][k - 1] : 0;
                    tmp += k + 1 <= j ? dp[k + 1][j] : 0;
                    dp[i][j] = min(dp[i][j],tmp);
                }
            }
        }
        cout << dp[1][n] << endl;

    }
    return 0;
}

Longest Palindromic Substring vs Longest Palindromic Subsequence

Longest Palindromic Substring
      f[i][j] means string[i...j] is palindromic.
        thus, f[i][j] = true if str[i] == str[j] && f[i + 1][j - 1] = true

Longest Palindromic Subsequence
        g[i][j] means the maximum length of palindromic subsequence in string[i...j]
        thus, g[i][j] = max(g[i + 1][j - 1] + 1 (if str[i] == str[j]),
                                     g[i + 1][j],
                                     g[i][j - 1]);

Maximum size square sub-matrix with all 1s

Solution
  dp[i][j] means the maximum size that ends with arr[i][j]
   dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

[leetcode]132. Palindrome Partitioning II

Problem
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution

enumerate the length of the last part partition which is a palindrome.

If we pre-calculate the array f[i][j] which means whether string[i...j] is a palindrome. 

    f[i][j] = f[i + 1][j - 1] && str[i] == str[j] where len >= 2

    f[i][j] = str[i] == str[j] where len < 2

let dp[i] means the mininum cuts of string[0...i], thus 

    dp[i] = 0 if string[0...i] is a palindrome itself.

    dp[i] = min(dp[j] + 1) where 1 <= j <= i   and string[i...j] is a palindrome.

Code

class Solution {
public:
 int minCut(string s) {
        int n = s.size();
        vector > f(n + 1,vector(n + 1,false));
        for (int len = 1;len <= n;len ++) {
            for (int i = 0;i + len - 1 < n;i ++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (len <= 2 || f[i + 1][j - 1])) {
                    f[i][j] = true;
                }
                else {
                    f[i][j] = false;
                }
            }
        }
        cout << f[0][1] << endl;
        vector dp(n + 1,0x3f3f3f3f);
        for (int i = 0;i < n;i ++) {
            if (f[0][i]) dp[i] = 0;
            else {
                for (int j = 1;j <= i;j ++) {
                    if (f[j][i]) {
                        dp[i] = min(dp[i],dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 2];
 }
};

Longest Bitonic Subsequence

Problem
    Longest Bitonic Subsequence

Examples:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

Solution
    max(lis[i] + rds[i] - 1) 1 <= i <= n

Tips
   lis[i] >= 1 && rds[i] >= 1 where i between 1 and n

Cutting a Rod

Problem

    give a rob of length n inches, try to split into several pieces. And try to max the total value.

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

Solution
    try to enumerate the length of the last piece.

Egg Dropping Puzzle

Problem

     Egg Dropping Puzzle

Solution

     maxmin

Code

#include <cstring>
#include <stdio.h>
#include <iostream>
using namespace std;

int T;
const int N = 55;
const int M = 1010;
int dp[N][M];
//dp[i][j] = min(max(dp[i - 1][x - 1],dp[i][j - x]));
int main() {
    scanf("%d",&T);
    memset(dp,0x3f,sizeof(dp));
    for (int i = 0;i <= 50;i ++) {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for (int j = 1;j <= 1000;j ++) {
        dp[1][j] = j;
    }

    for (int i = 2;i <= 50;i ++) {
        for (int j = 2;j <= 1000;j ++) {
            for (int k = 1;k <= j;k ++) {
                dp[i][j] = min(dp[i][j],max(dp[i - 1][k - 1],dp[i][j - k]) + 1);
            }
        }
    }
    while (T --) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        printf("%d %d\n",a,dp[b][c]);
    }
}

longest increasing subsequence VS strictly longest increasing subsequence

longest increasing subsequence

int n;
vector vec;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    cin >> n;
    for (int i = 0;i < n;i ++) {
        int tmp;
        scanf("%d",&tmp);
        vec.push_back(tmp);
    }
    fill(dp,dp + n,INF);
    int len = vec.size();
    for (int i = 0; i < len;i ++) {
        *upper_bound(dp,dp + n,vec[i]) = vec[i];
    }
    int ans = lower_bound(dp,dp + n,INF) - dp;
    cout << ans << endl;
}

strictly longest increasing subsequence

int n;
vector vec;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    cin >> n;
    for (int i = 0;i < n;i ++) {
        int tmp;
        scanf("%d",&tmp);
        vec.push_back(tmp);
    }
    fill(dp,dp + n,INF);
    int len = vec.size();
    for (int i = 0; i < len;i ++) {
        *lower_bound(dp,dp + n,vec[i]) = vec[i];
    }
    int ans = lower_bound(dp,dp + n,INF) - dp;
    cout << ans << endl;
}