Best travel

• Time : $O(tk * |ls|)$
• Space : $O(tk)$

c++

#include <vector>
using namespace std;
class BestTravel
{
public:
    static int chooseBestSum(int t, int k, std::vector<int>& ls);
};
int BestTravel::chooseBestSum(int t, int k, std::vector<int>& ls) {
    vector<vector<int>> dp(k,vector<int>(t + 1));
    for(auto l : ls) {
        for(int i = t - l; i >= 0; i--) {
            for(int j = k-2; j >= 0; j--) {
                if(dp[j][i]) dp[j+1][i+l] = 1;
            }
        }
        if(l <= t) dp[0][l] = 1;
    }
    for(int i = t; i >= 0; i--) if(dp[k-1][i]) return i;
    return -1;
}