Given a sequence of n integers, you have to find out the non-decreasing subsequence of length k with minimum sum. If no sequence exists output -1.
Examples :
Input : [58 12 11 12 82 30 20 77 16 86],
k = 3
Output : 39
{11 + 12 + 16}
Input : [58 12 11 12 82 30 20 77 16 86],
k = 4
Output : 120
{11 + 12 + 20 + 77}
Input : [58 12 11 12 82 30 20 77 16 86],
k = 5
Output : 206
Let solve(i, k) be the minimum sum of a subsequence of size k ending at index i. Then there would be two states:
1. Include current element. {solve(j, k-1) + a[i]}
2. Exclude current element. {solve(j, k)}
Our recurrence state would be:
dp[i][k] = min(solve(j, k-1) + a[i], solve(j, k)) if a[i] >= a[j] for all 0 <= j <= i.
C++
// C++ program to find Non-decreasing sequence// of size k with minimum sum#include <bits/stdc++.h>using namespace std;const int MAX = 100;const int inf = 2e9;// Global table used for memoizationint dp[MAX][MAX];void initialize(){ for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i][j] = -1;}int solve(int arr[], int i, int k){ // If already computed if (dp[i][k] != -1) return dp[i][k]; // Corner cases if (i < 0) return inf; if (k == 1) { int ans = inf; for (int j = 0; j <= i; j++) ans = min(ans, arr[j]); return ans; } // Recursive computation. int ans = inf; for (int j = 0; j < i; j++) if (arr[i] >= arr[j]) ans = min(ans, min(solve(arr, j, k), solve(arr, j, k - 1) + arr[i])); else { ans = min(ans, solve(arr, j, k)); } dp[i][k] = ans; return dp[i][k];}// Driver codeint main(){ initialize(); int a[] = { 58, 12, 11, 12, 82, 30, 20, 77, 16, 86 }; int n = sizeof(a) / sizeof(a[0]); int k = 4; cout << solve(a, n - 1, k) << endl; return 0;} |
Java
// Java program to find Non-decreasing sequence// of size k with minimum sumimport java.io.*;import java.util.*;class GFG { public static int MAX = 100; public static int inf = 1000000; // Table used for memoization public static int[][] dp = new int[MAX][MAX]; // initialize static void initialize() { for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i][j] = -1; } // Function to find non-decreasing sequence // of size k with minimum sum static int solve(int arr[], int i, int k) { // If already computed if (dp[i][k] != -1) return dp[i][k]; // Corner cases if (i < 0) return inf; if (k == 1) { int ans = inf; for (int j = 0; j <= i; j++) ans = Math.min(ans, arr[j]); return ans; } // Recursive computation int ans = inf; for (int j = 0; j < i; j++) if (arr[i] >= arr[j]) ans = Math.min(ans, Math.min(solve(arr, j, k), solve(arr, j, k - 1) + arr[i])); else ans = Math.min(ans, solve(arr, j, k)); dp[i][k] = ans; return dp[i][k]; } // driver program public static void main(String[] args) { initialize(); int a[] = { 58, 12, 11, 12, 82, 30, 20, 77, 16, 86 }; int n = a.length; int k = 4; System.out.println(solve(a, n - 1, k)); }}// Contributed by Pramod Kumar |
Python3
# Python program to find Non-decreasing sequence# of size k with minimum sum # Global table used for memoizationdp = []for i in range(10**2 + 1): temp = [-1]*(10**2 + 1) dp.append(temp) def solve(a, i, k): if dp[i][k] != -1: # Memoization return dp[i][k] elif i < 0: # out of bounds return float('inf') # when there is only one element elif k == 1: return min(a[: i + 1]) # Else two cases # 1 include current element # solve(a, j, k-1) + a[i] # 2 ignore current element # solve(a, j, k) else: ans = float('inf') for j in range(i): if a[i] >= a[j]: ans = min(ans, solve(a, j, k), solve(a, j, k-1) + a[i]) else: ans = min(ans, solve(a, j, k)) dp[i][k] = ans return dp[i][k] # Driver codea = [58, 12, 11, 12, 82, 30, 20, 77, 16, 86] print (solve(a, len(a)-1, 4)) |
C#
// C# program to find Non-decreasing sequence// of size k with minimum sumusing System;class GFG { public static int MAX = 100; public static int inf = 1000000; // Table used for memoization public static int[, ] dp = new int[MAX, MAX]; // initialize static void initialize() { for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) dp[i, j] = -1; } // Function to find non-decreasing // sequence of size k with minimum sum static int solve(int[] arr, int i, int k) { int ans = 0; // If already computed if (dp[i, k] != -1) return dp[i, k]; // Corner cases if (i < 0) return inf; if (k == 1) { ans = inf; for (int j = 0; j <= i; j++) ans = Math.Min(ans, arr[i]); return ans; } // Recursive computation ans = inf; for (int j = 0; j < i; j++) if (arr[i] >= arr[j]) ans = Math.Min(ans, Math.Min(solve(arr, j, k), solve(arr, j, k - 1) + arr[i])); else ans = Math.Min(ans, solve(arr, j, k)); dp[i, k] = ans; return dp[i, k]; } // driver program public static void Main() { initialize(); int[] a = { 58, 12, 11, 12, 82, 30, 20, 77, 16, 86 }; int n = a.Length; int k = 4; Console.WriteLine(solve(a, n - 1, k)); }}// This code is contributed by vt_m |
Javascript
<script> // Javascript program to find // Non-decreasing sequence // of size k with minimum sum let MAX = 100; let inf = 1000000; // Table used for memoization let dp = new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); for (let j = 0; j < MAX; j++) { dp[i][j] = 0; } } // initialize function initialize() { for (let i = 0; i < MAX; i++) for (let j = 0; j < MAX; j++) dp[i][j] = -1; } // Function to find non-decreasing sequence // of size k with minimum sum function solve(arr, i, k) { // If already computed if (dp[i][k] != -1) return dp[i][k]; // Corner cases if (i < 0) return inf; if (k == 1) { let ans = inf; for (let j = 0; j <= i; j++) ans = Math.min(ans, arr[j]); return ans; } // Recursive computation let ans = inf; for (let j = 0; j < i; j++) if (arr[i] >= arr[j]) ans = Math.min(ans, Math.min(solve(arr, j, k), solve(arr, j, k - 1) + arr[i])); else ans = Math.min(ans, solve(arr, j, k)); dp[i][k] = ans; return dp[i][k]; } initialize(); let a = [ 58, 12, 11, 12, 82, 30, 20, 77, 16, 86 ]; let n = a.length; let k = 4; document.write(solve(a, n - 1, k)); </script> |
Output:
120
This article is contributed by Anuj Shah. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
