生活随笔
收集整理的这篇文章主要介绍了
动态规划——坐标型位操作型
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
动态规划——坐标型&位操作型
坐标型动态规划——带阻碍的唯一路径序列型动态规划——油漆房子划分型动态规划——解密方式坐标型动态规划——最长上升连续子序列坐标型动态规划——最小路径和坐标型动态规划——炸弹袭击位操作型动态规划——计算二进制中 1 的个数
1. 坐标型动态规划——带阻碍的唯一路径
https://www.lintcode.com/problem/unique-paths-ii/description
题目描述：
- 给定 m 行 n 列的网格，有一个机器人从左上角（0,0）出发，每一步可以向下或者向右走一步。
- 网格中有些地方有障碍，机器人不能通过障碍格。
- 问有多少种不同的方式走到右下角？
public int uniquePathsWithObstacles(int[][] board
) {int m
= board
.length
;int n
= board
[0].length
;if (m
== 0 || n
== 0) {return 0;}int[][] f
= new int[m
][n
];for (int i
= 0; i
< m
; i
++) {for (int j
= 0; j
< n
; j
++) {if (board
[i
][j
] == 1) {f
[i
][j
] = 0;continue;}if (i
== 0 || j
== 0) {f
[i
][j
] = 1;continue;}if (i
> 0) {f
[i
][j
] += f
[i
- 1][j
];}if (j
> 0) {f
[i
][j
] += f
[i
][j
- 1];}}}return f
[m
- 1][n
- 1];}
2. 序列型动态规划——油漆房子
https://www.lintcode.com/problem/paint-house/description
题目描述：
- 有一排 N 栋房子，每栋房子要涂成 3 种颜色中的一种：红、蓝、绿。
- 任何两栋相邻房子不能涂成相同的颜色
- 第 i 栋房子染成红色、蓝色、绿色的花费分别是 cost[i][0]，cost[i][1]，cost[i][2]
- 问最少需要花多少钱油漆这些房子？
public int minCost(int[][] c
) {int n
= c
.length
;if (n
== 0) {return 0;}int[][] f
= new int[n
+ 1][3];f
[0][0] = f
[0][1] = f
[0][2] = 0;for (int i
= 1; i
<= n
; i
++) {for (int j
= 0; j
< 3; j
++) {f
[i
][j
] = Integer
.MAX_VALUE
;for (int k
= 0; k
< 3; k
++) {if (j
!= k
) {f
[i
][j
] = Math
.min(f
[i
][j
], f
[i
- 1][k
] + c
[i
- 1][j
]);}}}}return Math
.min(f
[n
][0], Math
.min(f
[n
][1], f
[n
][2]));}
3. 划分型动态规划——解密方式
https://www.lintcode.com/problem/decode-ways/description
题目描述：
- 有一段由 A-Z 组成的字符串信息被加密成数字串。
- 加密方式为：A->1, B->2, …Z->26
- 给定加密后的数字串 S[0…N-1]，问有多少种方式解密成字符串？
public int numDecodings(String ss
) {char[] s
= ss
.toCharArray();int n
= s
.length
;if (n
== 0) {return 0;}int[] f
= new int[n
+ 1];f
[0] = 1;int i
, j
;for (i
= 1; i
<= n
; i
++) {f
[i
] = 0;if (s
[i
- 1] >= '1' && s
[i
- 1] <= '9') {f
[i
] += f
[i
- 1];}if (i
> 1) {j
= 10 * (s
[i
- 2] - '0') + (s
[i
- 1] - '0');if (j
>= 10 && j
<= 26) {f
[i
] += f
[i
- 2];}}}return f
[n
];}
4. 坐标型动态规划——最长上升连续子序列
题目描述：
- 给定 a[0],…,a[n-1]
- 找到最长的连续子序列 i，i+1，i+2，…j，使得 a[i] < a[i+1] < a[j]，或者 a[i] > a[i+1] > …>a[j]，输出长度 j-i+1.
例子：
输入：[5,1,2,3,4]
输出：4（子序列 1,2,3,4）
public int longestIncreasingContinuousSubsequence(int[] nums
) {int n
= nums
.length
;if (n
== 0) {return 0;}int r1
= LIS(nums
, n
);int i
, j
, temp
;i
= 0;j
= n
- 1;while (i
< j
) {temp
= nums
[i
];nums
[i
] = nums
[j
];nums
[j
] = temp
;i
++;j
--;}int r2
= LIS(nums
, n
);return r1
>= r2
? r1
: r2
;}private int LIS(int[] nums
, int n
) {int i
;int[] f
= new int[n
];int res
= 0;for (i
= 0; i
< n
; i
++) {f
[i
] = 1;if (i
> 0 && nums
[i
] > nums
[i
- 1]) {f
[i
] = f
[i
- 1] + 1;}res
= Math
.max(res
, f
[i
]);}return res
;}
5. 坐标型动态规划——最小路径和
https://www.lintcode.com/problem/minimum-path-sum/description
题目描述：
- 给定 m 行 n 列的网格，每个格子（i，j）里都一个非负数 A[i][j]
- 求一个左上角（0,0）到右下角的路径，每一步只能向下或者向右走一步，使得路径上的格子里的数字之和最小
- 输出最小数字和
public int minPathSum(int[][] board
) {int m
= board
.length
;int n
= board
[0].length
;if (m
== 0 || n
== 0) {return 0;}int[][] f
= new int[m
][n
];for (int i
= 0; i
< m
; i
++) {for (int j
= 0; j
< n
; j
++) {if (i
== 0 && j
== 0) {f
[i
][j
] = board
[0][0];continue;}int t
= Integer
.MAX_VALUE
;if (i
> 0) {t
= Math
.min(t
, f
[i
- 1][j
] );}if (j
> 0) {t
= Math
.min(t
, f
[i
][j
- 1] );}f
[i
][j
] = t
+board
[i
][j
];}}return f
[m
-1][n
-1];}
滚动数组方式：将 f 的 i 位置 %2.
public int minPathSum(int[][] board
) {int m
= board
.length
;int n
= board
[0].length
;if (m
== 0 || n
== 0) {return 0;}int[][] f
= new int[2][n
];for (int i
= 0; i
< m
; i
++) {for (int j
= 0; j
< n
; j
++) {if (i
== 0 && j
== 0) {f
[i
% 2][j
] = board
[0][0];continue;}int t
= Integer
.MAX_VALUE
;if (i
> 0) {t
= Math
.min(t
, f
[1 - i
% 2][j
]);}if (j
> 0) {t
= Math
.min(t
, f
[i
% 2][j
- 1]);}f
[i
% 2][j
] = t
+ board
[i
][j
];}}return f
[(m
- 1) % 2][n
- 1];}
6. 坐标型动态规划——炸弹袭击
https://www.lintcode.com/problem/bomb-enemy/description
题目描述：
- 有一个 M*N 的网格，每个格子可能是空的，可能有一个敌人，可能有一堵墙
- 只能在某个空格子里放一个炸弹，炸弹会炸死所有同行同列的敌人，但是不能穿透墙
- 最多能炸死几个敌人
public int maxKilledEnemies(char[][] A
) {if (A
== null
|| A
.length
== 0 || A
[0].length
== 0) {return 0;}int m
= A
.length
;int n
= A
[0].length
;int[][] up
= new int[m
][n
];int[][] down
= new int[m
][n
];int[][] left
= new int[m
][n
];int[][] right
= new int[m
][n
];int i
, j
, t
;for (i
= 0; i
< m
; ++i
) {for (j
= 0; j
< n
; ++j
) {up
[i
][j
] = 0;if (A
[i
][j
] != 'W') {if (A
[i
][j
] == 'E') {up
[i
][j
] = 1;}if (i
- 1 >= 0) {up
[i
][j
] += up
[i
-1][j
];}}}}for (i
= m
- 1; i
>= 0; --i
) {for (j
= 0; j
< n
; ++j
) {down
[i
][j
] = 0;if (A
[i
][j
] != 'W') {if (A
[i
][j
] == 'E') {down
[i
][j
] = 1;}if (i
+ 1 < m
) {down
[i
][j
] += down
[i
+1][j
];}}}}for (i
= 0; i
< m
; ++i
) {for (j
= 0; j
< n
; ++j
) {left
[i
][j
] = 0;if (A
[i
][j
] != 'W') {if (A
[i
][j
] == 'E') {left
[i
][j
] = 1;}if (j
- 1 >= 0) {left
[i
][j
] += left
[i
][j
-1];}}}}for (i
= 0; i
< m
; ++i
) {for (j
= n
- 1; j
>= 0; --j
) {right
[i
][j
] = 0;if (A
[i
][j
] != 'W') {if (A
[i
][j
] == 'E') {right
[i
][j
] = 1;}if (j
+ 1 < n
) {right
[i
][j
] += right
[i
][j
+1];}}}}int res
= 0;for (i
= 0; i
< m
; ++i
) {for (j
= 0; j
< n
; ++j
) {if (A
[i
][j
] == '0') {t
= up
[i
][j
] + down
[i
][j
] + left
[i
][j
] + right
[i
][j
];res
= Math
.max(res
,t
);}}}return res
;}
7. 位操作型动态规划——计算二进制中 1 的个数
https://www.lintcode.com/problem/counting-bits/description
题目描述：
- 给定 N，要求输出 0,1，…，N 的每个数的二进制表示里1 的个数。
public int[] countBits(int num
) {int[] f
= new int[num
+ 1];f
[0] = 0;for (int i
= 1; i
<= num
; i
++) {f
[i
] = (i
% 2) + f
[i
>> 1];}return f
;}
总结
以上是生活随笔为你收集整理的动态规划——坐标型位操作型的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
