Algorithm
lc63_不同路径 II
思路:
暴力模拟，向下向右走，直接广度优先遍历+剪枝，每次走到终点加一次ans。
但是显然有导致很多冗余计算，可能会导致超时。
可以dp优化，每个点都来自左边或者上边，所以dp[i][j] = dp[i-1][j] + dp[i][j-1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
impl Solution {
pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
let m = obstacle_grid.len();
let n = obstacle_grid[0].len();
let mut dp = vec![vec![0; n]; m];
if obstacle_grid[0][0] == 0 {
dp[0][0] = 1;
}
for i in 0..m {
for j in 0..n {
if obstacle_grid[i][j] == 1 {
continue;
}
if i > 0 {
dp[i][j] += dp[i - 1][j];
}
if j > 0 {
dp[i][j] += dp[i][j - 1];
}
}
}
dp[m - 1][n - 1]
}
}
|
题解用了滚动数组，把空间复杂度又降了一个维度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
impl Solution {
pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
let n = obstacle_grid.len();
let m = obstacle_grid[0].len();
let mut f = vec![0; m];
f[0] = if obstacle_grid[0][0] == 0 { 1 } else { 0 };
for i in 0..n {
for j in 0..m {
if obstacle_grid[i][j] == 1 {
f[j] = 0;
} else if j > 0 && obstacle_grid[i][j - 1] == 0 {
f[j] += f[j - 1];
}
}
}
f[m - 1]
}
}
|
Review
为什么你应该从个人数据中获利？【TED演讲】
生产队进化成私有制企业，从而让大家从贫困走向富裕。
进而暗示，数据从大公司垄断，到个人私有，也会创造巨大的经济效应。
这里其实和web3的数据私有化有异曲同工之妙。定义新的生产关系，创造新的经济效应。
没有数据中间商赚差价，直接每个人的数据变成自己的钱。
希望未来 AI + web3 私人数据能让大多数人摆脱贫困，都能有机会享受科技，享受生活。
Tips
三个月成为「meme 届币安」，关于 Moonshot 你不知道的那些事
Moonshot 的成功证明: 简单易用从来都不是伪命题，meme这种争分抢秒的玩法，只要做到极致简单易用数据及时。
就算被收3-5%的手续费，也依然有大量用户。
Share
Kamino介绍
https://x.com/wolfdan666666/status/1888619080279883850