我有一个关于使用memoization(DP)实现Fibonacci序列的快速问题.我正在使用HashTable,但由于某种原因,该表似乎永远不会包含这些元素.我插入一个print语句,以便在从哈希表中读取值时打印出来,似乎这种情况从未发生过.我觉得这是一个简单的修复,但我没有看到它.
public static int getFib(int n) {
HashMap<Integer, Integer> dictionary = new HashMap<Integer, Integer>();
if (n <= 2)
return 1;
else if (dictionary.containsKey(n)) {
System.out.println("Reading From Table");
return dictionary.get(n);
} else {
int val = getFib(n - 1) + getFib(n - 2);
dictionary.put(n, val);
return val;
}
}
我知道:
int fib(int n)
{
if (n == 0 || n == 1)
return 1;
return fib(n ? 1)+ fib(n ? 2);
}
当n = 5时,fib(5)评估为:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
请注意,每个基本元素被多次使用,有没有办法使用map来存储前一个值,只需要做fib(n - 1)+ fib(n - 2)吗？
给定N个工作,其中每个工作由以下三个元素表示.
1)开始时间
2)完成时间.
3)利润或价值相关.
找到作业的最大利润子集,使子集中没有两个作业重叠.
我知道一个动态编程解决方案,其复杂度为O(N ^ 2)(接近LIS,我们必须检查以前的元素,我们可以合并当前间隔并采用合并给出最大值的区间直到第i个这个解决方案可以使用二进制搜索和简单排序进一步改进为O(N*log N)!
但是我的朋友告诉我,甚至可以通过使用Segment Trees和二分搜索来解决它!我不知道我将在哪里使用Segment Tree以及如何使用.
你能帮我吗？
根据要求,抱歉没有评论
我正在做的是根据起始索引进行排序,通过合并先前的时间间隔和它们的最大可获得值,将最大可获得值存储到DP [i]中i!
void solve()
{
int n,i,j,k,high;
scanf("%d",&n);
pair < pair < int ,int>, int > arr[n+1];// first pair represents l,r and int alone shows cost
int dp[n+1];
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
scanf("%d%d%d",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
std::sort(arr,arr+n); // by default sorting on the basis of starting index
for(i=0;i<n;i++)
{
high=arr[i].second;
for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
if(arr[i].first.first>=arr[j].first.second)
high=std::max(high …language-agnostic algorithm dynamic-programming segment-tree
我是动态编程的新手,根据我的理解,动态编程是您使用计算结果来检查函数是否正确的地方.在接受采访时我被要求实施一种方法,以检查是否n是2的力量.所以,我想出了这个.
def isPowerOfTwo(self, n):
power_of_two = [1]
is_power_of_two = False
if n == 0:
return False
if n == 1:
return True
while True:
power_of_two.append(power_of_two[-1] * 2)
if n == power_of_two[-1]:
is_power_of_two = True
break
if power_of_two[-1] > n:
break
return is_power_of_two
问题陈述 :
您位于位置(x1,x2,...,xN)的N维网格中.网格的尺寸为(D1,D2,...... DN).在一个步骤中,您可以在N个维度中的任何一个中前进或后退一步.(因此总有2×N可能的不同动作).你有多少种方法可以采取M步,这样你就不会在任何时候离开网格？如果在任何点xi,你离开网格,xi≤0或xi> Di.
输入格式
第一行包含测试用例的数量T.T测试用例如下.对于每个测试用例,第一行包含N和M,第二行包含x1,x2,...,xN,第3行包含D1,D2,...,DN.
输出格式
输出T线,一个对应于每个测试用例.由于答案可能非常大,因此输出模数为1000000007.
约束
1≤T≤10
1≤N≤10
1≤M≤300
1≤Di≤100
1≤xi≤Di
样本输入
1
2 3
1 1
2 3
样本输出
12
如果这是1D,解决方案可以是这样的:solve(i + 1)+ solve(i-1);
在2D中:求解(i + 1,j)+求解(i-1,j)+求解(i,j + 1)+求解(i,j-1); 我如何为N Dimensions编程？它们是如上所述制作递归语句的一些常规步骤,可以帮助制作递归语句
我看到的大多数解决方案都是自下而上或自上而下的方式,我无法理解它们？是他们理解他们的任何方式,因为我总是使用递归+ memoization练习dp我觉得很难理解它们
如何做记忆？要使用哪种数据结构？,在哪里使用modulo 1e 7(仅在最终答案中)？
更新 感谢BARNEY解决方案,但在大多数情况下获得TLE如何更快地执行代码:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
public class Grid_Walking {
private static String[] n;
private static int moves;
private static HashMap<String, Integer> hm;
private static BufferedReader …两个玩家正在玩游戏,其中每个玩家必须在每个回合中选择1,2,3或4个硬币.总共有n个硬币.拿起最后一枚硬币的玩家,他赢了.设计一个赢得比赛的策略.
什么是解决问题的算法策略,以便我可以赢得比赛,假设我是其中一个球员？
此分配旨在为原始计算器实现动态编程方法，该方法只能加1，乘以2和乘以3。因此，在输入n的情况下，确定达到n的最小操作数。我已经实现了非常幼稚的dp或我认为是dp的方法。它不起作用。我没有人要问。对于n = 5的输入，以下输出为：（[0，1，2，2，2，3，4]，[1，1，2，3，4，5]），而对于列表编号= [1、2、4、5]或[1、3、4、5]。一些帮助将不胜感激。
def DPmin_operations(n):
numbers = []
minNumOperations = [0]*(n+1)
numOps = 0
numbers.append(1)
for k in range(1,n+1):
minNumOperations[k] = 10000
# for *3 operator
if k % 3 == 0:
numOps = minNumOperations[k//3] + 1
if numOps < minNumOperations[k]:
minNumOperations[k] = numOps
numbers.append(k)
# for *2 operator
elif k % 2 == 0:
numOps = minNumOperations[k//2] + 1
if numOps < minNumOperations[k]:
minNumOperations[k] = numOps
numbers.append(k)
# for + 1 operator
elif k >= 1:
numOps = …如果允许预处理,则在给定范围的未排序数组中查找最大元素的最快方法是什么.
我们有初始数组A = {3,2,4,5,1},我们需要对它进行预处理,然后我们回答q个查询.
查询示例,如果查询中指定的范围是[0,2],则此范围中的最大元素为4.
问题是如果只能以两种方式移动,找到从(1,1)(如果存在)到达(m,n)所需的最小步骤数的路径:(x,y)=(x + y,y)或(x,y)=(x,x + y).
我尝试用动态编程来做这个,但是m和n最多可以达到10 ^ 25,所以这是不可行的.如何调整我的解决方案以使其适用于大量输入？还是有其他方法吗？
我正在尝试实现以下C++算法的Java版本:
void constructPrintLIS(int arr[], int n)
{
std::vector< std::vector<int> > L(n);
L[0].push_back(arr[0]);
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if ((arr[i] > arr[j]) &&
(L[i].size() < L[j].size() + 1))
{
L[i] = L[j];
cout << true << endl;
}
else
{
cout << false << endl;
}
}
L[i].push_back(arr[i]);
}
std::vector<int> max = L[0];
for (std::vector<int> x : L)
{
if (x.size() > max.size())
{
max = …