context
当前状态是由前面两个相邻的状态决定的
状态可以用array来保存，或者用常量保存，但是要知道变更状态
dp[i] = option(dp[i - 1], dp[i - 2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class //自上而下
{
int[] fib_cache = new int[31];
public int fib(int N)
{
if(N <= 1)
return N;
else if(fib_cache[N] != 0)
return fib_cache[N];
else
return fib_cache[N] = fib(N - 1) + fib(N - 2);
}
}
class //自下而上
{
public int fib(int N)
{
if(N <= 1)
return N;
int a = 0, b = 1;
while(N-- > 1)
{
int sum = a + b;
a = b;
b = sum;
}
return b;
}
}
|
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
one can reach ith step in one of two ways:
so the problem of numbers of ways to ith step breaks up into the sum of ways to (i - 1)th step and (i - 2)th step
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class {
public int climbStairs(int n) {
if(n == 1)
return 1;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
|
the i-th step has some non-negative cost cost[i] assigned (0 indexed).
1
2
3
4
5
6
7
8
9
10
11
|
class {
public int minCostClimbingStairs(int[] cost) {
int f1 = cost[0], f2 = cost[1];
for(int i = 2; i < cost.length; i++) {
int f_cur = cost[i] + Math.min(f1, f2);
f1 = f2;
f2 = f_cur;
}
return Math.min(f1, f2);
}
}
|
从0位置到当前位置长度能够解码出字符串的数目，由当前位置长度减一和减二的数目决定。
如果当前的位置能够解码出一个字母就算上前面一位的数目，如果当前位置和前一位能够组成另一个字母就算上更前面的数目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class {
public int numDecodings(String s) {
if(s.length() < 1 || s.charAt(0) == '0')
return 0;
int[] dp = new int[s.length()];
dp[0] = 1;
for(int i = 1; i < s.length(); i++) {
if(s.charAt(i) != '0')
dp[i] = dp[i - 1];
if(s.charAt(i - 1) != '0') {
int num = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
if(num <= 26)
dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
}
}
return dp[s.length() - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}
|
解释：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75931/Easiest-JAVA-solution-with-explanations
合理使用状态表示，以及状态的转换
近期评论